Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs
From MaRDI portal
Publication:3467876
DOI10.1007/978-3-319-26626-8_46zbMath1473.68216MaRDI QIDQ3467876
Abhiruk Lahiri, C. R. Subramanian, Joydeep Mukherjee
Publication date: 5 February 2016
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_46
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
On approximating MIS over B1-VPG graphs*, Computing maximum independent set on outerstring graphs and their relatives, Collision-free routing problem with restricted L-path, Bounds on the bend number of split and cocomparability graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Planar graphs have 1-string representations
- Planar Graphs as VPG-Graphs
- Equilateral L-Contact Graphs
- Intersection Graphs of L-Shapes and Segments in the Plane
- $1$-string $B_2$-VPG representation of planar graphs
- Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
- Vertex Intersection Graphs of Paths on a Grid
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
- Posets and VPG graphs