An algorithm for the maximum weight independent set problem on outerstring graphs
From MaRDI portal
Publication:680149
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
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
