Hardness and approximation for L-EPG and B₁-EPG graphs

DOI10.1016/J.DAM.2019.10.004MaRDI QIDQ2184686zbMATH OpenOpenAlexFDO

Authors Dror Epstein, Martin Charles Golumbic, Abhiruk Lahiri, Gila Morgenstern

Publication date 29 May 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.10.004

zbMATH Keywords

paths on a gridedge intersection graphB1-EPG graphs\(k\)-simplicial graphsfully-subdivided graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Approximation algorithms for \(B _{1}\)-EPG graphs
• On independent set in \(B_1\)-EPG graphs
• On independent set on B1-EPG graphs
• Edge intersection graphs of \(L\)-shaped paths in grids
• On edge intersection graphs of paths with 2 bends

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 2065154 (Why is no real title available?)
• scientific article; zbMATH DE number 7272507 (Why is no real title available?)
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Approximation algorithms for \(B _{1}\)-EPG graphs
• Approximation algorithms for intersection graphs
• Characterizations of cographs as intersection graphs of paths on a grid
• Clique coloring \(B_1\)-EPG graphs
• Edge intersection graphs of \(L\)-shaped paths in grids
• Edge intersection graphs of single bend paths on a grid
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Edge-intersection graphs of boundary-generated paths in a grid
• Edge-intersection graphs of grid paths: the bend-number
• On edge intersection graphs of paths with 2 bends
• On edge-intersection graphs of \(k\)-bend paths in grids
• On independent set on B1-EPG graphs
• On split \(B_1\)-EPG graphs
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Optimization problems in multiple-interval graphs
• Proper circular arc graphs as intersection graphs of paths on a grid
• Scheduling Split Intervals
• Single bend paths on a grid have strong Helly number 4: errata atque emendationes ad ``Edge intersection graphs of single bend paths on a grid
• Some properties of edge intersection graphs of single-bend paths on a grid
• The Complexity of Coloring Circular Arcs and Chords
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• The complexity of Helly-\(B_1\) EPG graph recognition
• VPG and EPG bend-numbers of Halin graphs

Cited in

(9)

• On independent set on B1-EPG graphs
• Computing maximum cliques in \(B_2\)-EPG graphs
• scientific article; zbMATH DE number 7272507 (Why is no real title available?)
• Edge intersection graphs of \(L\)-shaped paths in grids
• Maximum independent set on \(B_1\)-VPG graphs
• On independent set in \(B_1\)-EPG graphs
• Approximating domination on intersection graphs of paths on a grid
• Approximation algorithms for \(B _{1}\)-EPG graphs
• On split \(B_1\)-EPG graphs

This page was built for publication: Hardness and approximation for L-EPG and \(B_1\)-EPG graphs

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