scientific article; zbMATH DE number 5842466

MaRDI QIDQ3070898zbMATH OpenFDO

Authors George Christodoulou, V. Zissimopoulos

Publication date 28 January 2011

zbMATH Keywords

algorithmchordal graphsinterval graphsmaximum independent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• On-line models and algorithms for max independent set
• Graph-Theoretic Concepts in Computer Science
• An optimal maximal independent set algorithm for bounded-independence graphs
• On the maximum independent set problem in graphs of bounded maximum degree
• On minimum maximal independent sets of a graph
• On the number of maximum independent sets of graphs
• On the number of maximal independent sets in a graph
• The complexity of some problems on maximal independent sets in graphs
• On the maximum number of maximum independent sets in connected graphs
• Computing maximum independent set on outerstring graphs and their relatives

Cited in

(3)

• Online independent sets.
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Online independent set beyond the worst-case: secretaries, prophets, and periods

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3070898)