二维四角网格图的反馈数上界的改进

展开
  • 1. 华南师范大学数学科学学院, 广东广州 510631
刘岩 E-mail: liuyan@scnu.edu.cn

收稿日期: 2020-09-16

  网络出版日期: 2024-03-16

基金资助

广州市科技计划项目(202002030183);广东省自然科学基金(2021A1515012045);青海省自然科学基金(2020-ZJ-924)

版权

运筹学学报编辑部, 2024, 版权所有,未经授权。

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

摘要

$G=(V, E)$ 是简单图, 子集$F\subseteq V$。若由点集$V-F$ 导出的子图不含圈, 则称子集$F$ 是图$G$ 的反馈集。称反馈集的点数的最小值是图$G$ 的反馈数, 用$f(G)$ 表示,即,$f(G)=\min\{|F| : F$ 是图$G$ 的反馈集$\}$。Caragiannis等人给出了二维四角网格图反馈数的上界, 本文改进了其上界。

本文引用格式

苏雪丽, 李晓辉, 刘岩 . 二维四角网格图的反馈数上界的改进[J]. 运筹学学报, 2024 , 28(1) : 153 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.013

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.

参考文献

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.
文章导航

/