✦ LIBER ✦

A new bound on the feedback vertex sets in cubic graphs

✍ Scribed by Jiping Liu; Cheng Zhao

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 461 KB
Volume: 148
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00268-n

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper a new upper bound for the feedback set of cubic graphs is obtained. This result answers a question posed by Speckenmeyer (1986, 1988) in the field of feedback vertex set and improves several former results due to Bondy et al. (1987). Also this new bound is sharp in some cases.

📜 SIMILAR VOLUMES

On feedback vertex sets and nonseparatin

On feedback vertex sets and nonseparating independent sets in cubic graphs

✍ Ewald Speckenmeyer 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 341 KB

Let G be an undirected connected graph with n nodes. A subset F of nodes of G is a feedback vertex set (fvs) if G -F is a forest and a subset J of nodes of G is a nonseparating independent set (nsis) if no two nodes of J are adjacent and G -J is connected. f(G), z ( G ) denote the cardinalities of a

On the feedback vertex set problem in pe

On the feedback vertex set problem in permutation graphs

✍ Y. Daniel Liang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 603 KB

New bounds on the size of the minimum fe

New bounds on the size of the minimum feedback vertex set in meshes and butterflies

✍ Ioannis Caragiannis; Christos Kaklamanis; Panagiotis Kanellopoulos 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 113 KB

A Linear Time Algorithm for the Minimum-

A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs

✍ Shao-qiang Zhang; Guo-jun Li; Shu-guang Li 📂 Article 📅 2004 🏛 Institute of Applied Mathematics, Chinese Academy 🌐 English ⚖ 169 KB

On the nonseparating independent set pro

On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three

✍ Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 350 KB

This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.

A linear-time algorithm for the weighted

A linear-time algorithm for the weighted feedback vertex problem on interval graphs

✍ Chin Lung Lu; Chuan Yi Tang 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 459 KB

We present a linear-time algorithm for finding a minimum weighted feedback vertex set on interval graphs using the dynamic programming technique. Since the weighted feedback vertex problem, the weighted C3.1 problem, the maximum weighted 2-colorable subgraph problem and the maximum weighted 2-indepe