Maximum Independent Set in 2-Direction Outersegment Graphs

DOI10.1007/978-3-642-25870-1_15zbMath1341.05186OpenAlexW106108513MaRDI QIDQ3104773

Holger Flier, Anna Zych, Matúš Mihalák, Peter Widmayer

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_15

zbMATH Keywords

geometric representation of a graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

An algorithm for the maximum weight independent set problem on outerstring graphs

Cites Work

• Maximum weight independent sets and cliques in intersection graphs of filaments
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs requiring exponential representations
• The max clique problem in classes of string-graphs
• The complexity of domination problems in circle graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Recognizing string graphs is decidable
• Vertex Disjoint Paths for Dispatching in Railways.
• A Separator Theorem for String Graphs and its Applications
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Graph Classes: A Survey
• Recognizing string graphs in NP
• Unnamed Item
• Unnamed Item
• Unnamed Item