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

✍ Scribed by Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 350 KB
• Volume: 72
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90226-9

✦ Synopsis

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.