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

DOI10.1007/978-3-319-26626-8_46zbMath1473.68216OpenAlexW2403403088MaRDI 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

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

On approximating MIS over B1-VPG graphs*, Collision-free routing problem with restricted L-path, Computing maximum independent set on outerstring graphs and their relatives, 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