Paper Info
Title
Maximum independent set and maximum clique algorithms for overlap graphs
Abstract
We give polynomial time algorithms for the maximum independent set and maximum clique problems for classes of overlap graphs, assuming an overlap model is provided as input. The independent set algorithm applies to any class of overlap graphs for which the maximum weight independent set problem is polynomially solvable on the corresponding intersection graph class, where the vertex weights are nonnegative integers on which arithmetic operations can be performed in constant time. The maximum clique algorithm requires only that the overlap model satisfy the Helly property. In both cases, the size of the overlap model must be bounded by a polynomial in the size of the graph. The conditions for both algorithms are satisfied by the class of overlap graphs of subtrees in a tree, which contains chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs.
Year
DOI
Venue
2003
10.1016/S0166-218X(02)00418-3
Discrete Applied Mathematics
Keywords
Field
DocType
clique,circle graph,independent set algorithm,independent set problem,subtrees in a tree,maximum clique algorithm,corresponding intersection graph class,overlap graphs,algorithm,maximum weight,maximum clique problem,maximum independent set,independent set,circular-arc graph,subtree overlap graphs,chordal graph,satisfiability
Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Clique-sum,Algorithm,Independent set,Cograph,Treewidth,Mathematics,Split graph,Maximal independent set
Journal
Volume
Issue
ISSN
131
1
Discrete Applied Mathematics
Citations 
PageRank 
References 
9
0.69
8
Authors
2
Name
Order
Citations
PageRank
Eowyn Čenek1141.27
Lorna Stewart236128.05