On approximating MIS over B1-VPG graphs*

DOI10.1142/S1793830922500355OpenAlexW3206927202MaRDI QIDQ5057743

Joydeep Mukherjee, Abhiruk Lahiri, C. R. Subramanian

Publication date: 19 December 2022

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830922500355

zbMATH Keywords

independent setsapproximation algorithmscombinatorial optimisationgeometric intersection graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

On approximating MIS over B1-VPG graphs*

Cites Work

• Unnamed Item
• Intersection graphs of L-shapes and segments in the plane
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Finding a maximum independent set in a permutation graph
• The max clique problem in classes of string-graphs
• Modular decomposition and transitive orientation
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Approximation Algorithms for B 1-EPG Graphs
• Vertex Intersection Graphs of Paths on a Grid
• Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• On approximating MIS over B1-VPG graphs*