Polynomial algorithm for finding the largest independent sets in graphs without forks

A fork is a graph that is obtained from K 1,3 by subdividing one edge. It is known [6–8] that for K 1,3-free graphs the problem of finding the largest independent set can be solved in a polynomial time. In this paper, we prove that this is also true for the wider class of fork-free graphs.

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2004-01, Vol.135 (1), p.3-16
Main Author: Alekseev, V.E.
Format: Article
Language:English
Subjects:
Claw-free graphs
Graph
Independent set of vertices
Polynomial algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A fork is a graph that is obtained from K 1,3 by subdividing one edge. It is known [6–8] that for K 1,3-free graphs the problem of finding the largest independent set can be solved in a polynomial time. In this paper, we prove that this is also true for the wider class of fork-free graphs.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(02)00290-1