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

Feedback vertex set on cocomparability graphs

โœ Scribed by Satyan R. Coorg; C. Pandu Rangan

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
716 KB
Volume
26
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

๐Ÿ“œ 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

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.

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.