Maximum independent set in 2-direction outersegment graphs

DOI10.1007/978-3-642-25870-1_15MaRDI QIDQ3104773zbMATH OpenOpenAlexFDO

Authors Holger Flier, Matúš Mihalák, Anna Zych, 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 representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An algorithm for the maximum weight independent set problem on outerstring graphs
• Algorithm Theory - SWAT 2004
• Independent set of intersection graphs of convex objects in 2D
• Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
• Computing maximum independent set on outerstring graphs and their relatives

Cites work

• A separator theorem for string graphs and its applications
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Graph Classes: A Survey
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Recognizing string graphs in NP
• Recognizing string graphs is decidable
• String graphs requiring exponential representations
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs. II: Recognizing string graphs is NP-hard
• The complexity of domination problems in circle graphs
• The max clique problem in classes of string-graphs
• Vertex disjoint paths for dispatching in railways

Cited in

(5)

• Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
• On the size of outer-string representations
• Computing maximum independent set on outerstring graphs and their relatives
• Computing maximum independent set on outerstring graphs and their relatives
• An algorithm for the maximum weight independent set problem on outerstring graphs

This page was built for publication: Maximum independent set in 2-direction outersegment graphs

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