Maximum independent set on B₁-VPG graphs

DOI10.1007/978-3-319-26626-8_46MaRDI QIDQ3467876zbMATH OpenOpenAlexFDO

Authors Abhiruk Lahiri, Joydeep Mukherjee, C. R. Subramanian

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

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

Recommendations

• On independent set on B1-EPG graphs
• On independent set in \(B_1\)-EPG graphs
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Algorithm Theory - SWAT 2004

Cites work

• 1-string B₂-VPG representation of planar graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Computing the independence number of intersection graphs
• Equilateral L-contact graphs
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• Intersection graphs of L-shapes and segments in the plane
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Planar graphs as VPG-graphs
• Planar graphs have 1-string representations
• Posets and VPG graphs
• Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
• The Rectilinear Steiner Tree Problem is NP-Complete
• Vertex Intersection Graphs of Paths on a Grid

Cited in

(9)

• Collision-free routing problem with restricted L-path
• On independent set in \(B_1\)-EPG graphs
• Bounds on the bend number of split and cocomparability graphs
• On independent set on B1-EPG graphs
• On approximating MIS over B1-VPG graphs*
• Computing maximum independent set on outerstring graphs and their relatives
• Computing maximum independent set on outerstring graphs and their relatives
• Maximum bipartite subgraphs of geometric intersection graphs
• Approximation of MWIS on geometric intersection graphs

This page was built for publication: Maximum independent set on \(B_1\)-VPG graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467876)