Computing maximum independent set on outerstring graphs and their relatives
DOI10.1016/j.comgeo.2021.101852zbMath1486.05222arXiv1903.07024OpenAlexW3215765620MaRDI QIDQ5918655
Anil Maheshwari, Prosenjit Bose, Saeed Mehrabi, J. Mark Keil, Paz Carmi, Michiel H. M. Smid, Debajyoti Mondal
Publication date: 8 April 2022
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.07024
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Intersection graphs of L-shapes and segments in the plane
- Approximation algorithms for maximum independent set of pseudo-disks
- An algorithm for the maximum weight independent set problem on outerstring graphs
- Weakly transitive orientations, Hasse diagrams and string graphs
- An output sensitive algorithm for computing a maximum independent set of a circle graph
- String graphs. I: The number of critical nonstring graphs is infinite
- New clique and independent set algorithms for circle graphs
- Which problems have strongly exponential complexity?
- Approximating domination on intersection graphs of paths on a grid
- Algorithmic graph theory and perfect graphs
- On grounded \(\llcorner\)-graphs and their relatives
- Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
- Independent set of intersection graphs of convex objects in 2D
- Seidel Minor, Permutation Graphs and Combinatorial Properties
- Vertex Intersection Graphs of Paths on a Grid
- Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs
- Intersection Graphs of Rays and Grounded Segments
- Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
- Algorithms and Computation
- Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Computing maximum independent set on outerstring graphs and their relatives
This page was built for publication: Computing maximum independent set on outerstring graphs and their relatives
