On approximating MIS over B1-VPG graphs*
From MaRDI portal
Publication:5057743
DOI10.1142/S1793830922500355MaRDI 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
independent sets; approximation algorithms; combinatorial optimisation; geometric intersection graphs
90C27: Combinatorial optimization
05C10: Planar graphs; geometric and topological aspects of graph theory
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
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*
