Approximation Algorithms for B 1-EPG Graphs

DOI10.1007/978-3-642-40104-6_29zbMath1390.68499OpenAlexW2147119597MaRDI QIDQ2842171

Gila Morgenstern, Dror Epstein, Martin Charles Golumbic

Publication date: 12 August 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40104-6_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (14)

On edge intersection graphs of paths with 2 bends ⋮ Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ CPG graphs: some structural and hardness results ⋮ Edge intersection graphs of \(L\)-shaped paths in grids ⋮ On approximating MIS over B1-VPG graphs* ⋮ On independent set in \(B_1\)-EPG graphs ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Parameterized complexity of path set packing ⋮ On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ On the bend-number of planar and outerplanar graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Clique coloring \(B_1\)-EPG graphs

This page was built for publication: Approximation Algorithms for B 1-EPG Graphs