๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the feedback vertex set problem in permutation graphs

โœ Scribed by Y. Daniel Liang

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
603 KB
Volume
52
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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.

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

A new bound on the feedback vertex sets
A new bound on the feedback vertex sets in cubic graphs
โœ Jiping Liu; Cheng Zhao ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 461 KB

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.