Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs

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

Mathematics Subject Classification ID

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