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

DOI10.1016/j.comgeo.2016.05.001zbMath1378.05154OpenAlexW2382079786MaRDI QIDQ680149

Martin Vatshelle, Joseph S. B. Mitchell, J. Mark Keil, Dinabandhu Pradhan

Publication date: 22 January 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2016.05.001

zbMATH Keywords

maximum weight independent setoutersegment graphsouterstring graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (17)

Finding a Maximum Clique in a Grounded 1-Bend String Graph ⋮ Generalized disk graphs ⋮ On approximating MIS over B1-VPG graphs* ⋮ On dominating set of some subclasses of string graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ Faster multi-sided one-bend boundary labelling ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Polygon simplification by minimizing convex corners ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Unnamed Item ⋮ The Maximum Disjoint Routing Problem ⋮ Packing boundary-anchored rectangles and squares ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Boundary Labeling for Rectangular Diagrams

Cites Work

• Maximum weight independent sets and cliques in intersection graphs of filaments
• The clique problem in ray intersection graphs
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• 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
• Comparability graphs and intersection graphs
• The max clique problem in classes of string-graphs
• Intersection graphs of curves in the plane
• Label placement by maximum independent set in rectangles
• On the rectangle escape problem
• Vertex Disjoint Paths for Dispatching in Railways.
• Maximum Independent Set in 2-Direction Outersegment Graphs
• Noncrossing Subgraphs in Topological Layouts
• Data Mining with optimized two-dimensional association rules
• Every planar graph is the intersection graph of segments in the plane
• Topology of Thin Film RC Circuits
• String graphs and incomparability graphs
• Recognizing string graphs in NP
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An algorithm for the maximum weight independent set problem on outerstring graphs