中文

Operations Research Transactions >

2024 , Vol. 28 >Issue 1: 153 - 158

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.01.013

Improved upper bound of feedback number for 2-dimensional meshes

Expand
  • 1. School of Mathematical Science, South China Normal University, Guangzhou 510631, Guangdong, China

Received date: 2020-09-16

  Online published: 2024-03-16

Copyright

, 2024, All rights reserved, without authorization
Fold

Abstract

Let $G = (V, E)$ be a simple graph and $F$ be a subset of $V$. If the subgraph induced by the subset $V-F$ does not contain cycles, then $F$ is called a feedback set of $G$. The smallest value of the numbers of vertices in feedback sets is called the feedback number of $G$, denoted by $f(G)$, that is, $f(G)=\min\{|F| : F$ is a feedback set of $G\}$. Caragiannis et al. obtained the upper bounds of the feedback number of 2-dimensional meshes. In this paper, we improve the upper bounds.

Key words： 2-dimensional meshes; feedback vertex set; feedback number; acyclic subgraph

Cite this article

Xueli SU, Xiaohui LI, Yan LIU . Improved upper bound of feedback number for 2-dimensional meshes[J]. Operations Research Transactions, 2024 , 28(1) : 153 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.013

References

1 Wilfong G, Winkler P. Ring routing and wavelength translation [C]// Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998: 333-341.
2 Luccio F L , Sibeyn J F . Feedback vertex sets in mash-based networks[J]. Theoretical Computer Science, 2007, 383, 86- 101.
3 Xu X R , Hang Y Z , Zhang S J , et al. Feedback numbers of generalized Kautz digraphs $GK(3, n)$[J]. Computer Science, 2016, 43 (5): 13- 21.
4 Garey M R , Johnson D S . Computer and Intractability[M].
5 Peleg D. Local majority voting, small coalitions and controlling monopolies in graphs: A review [C]// Colloquium on Structural Information and Communication Complexity, Ottawa: Carleton University Press, 1996: 152-169.
6 Peleg D. Size bounds for dynamic monopolies [C]// Colloquium on Structural Information and Communication Complexity, Ottawa: Carleton University Press, 1997: 165-175.
7 Luccio F L . Almost exact minimum feedback vertex set in meshes and butterflies[J]. Information Processing Letters, 1998, 66 (2): 59- 64.
8 Caragiannis I , Kaklamanis C , Kanellopoulos P . New bounds on the size of the minimum feedback vertex set in meshes and butterflies[J]. Information Processing Letters, 2002, 83 (5): 275- 280.
Options
Outlines

/

〈 〉