On independent set in B₁-EPG graphs

DOI10.1016/J.DAM.2019.10.019MaRDI QIDQ2174555zbMATH OpenOpenAlexFDO

Authors Marin Bougeret, Steven Chaplick, Daniel Gonçalves, Christophe Paul, Stéphane Bessy

Publication date 21 April 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.019

zbMATH Keywords

\(B_1\)-EPG graphsapproximationFPTindependent setparameterized complexityPTAS

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On independent set on B1-EPG graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Approximation algorithms for \(B _{1}\)-EPG graphs
• On split \(B_1\)-EPG graphs
• Maximum independent set on \(B_1\)-VPG graphs

Cites work

• Approximation algorithms for \(B _{1}\)-EPG graphs
• Approximation algorithms for intersection graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for NP-complete problems on planar graphs
• Edge intersection graphs of \(L\)-shaped paths in grids
• Edge intersection graphs of single bend paths on a grid
• Edge-intersection graphs of grid paths: the bend-number
• On independent set on B1-EPG graphs
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Scheduling Split Intervals
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes

Cited in

(11)

• Computing maximum cliques in \(B_2\)-EPG graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• On independent set on B1-EPG graphs
• Approximation algorithms for \(B _{1}\)-EPG graphs
• The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent
• Maximum independent set on \(B_1\)-VPG graphs
• On approximating MIS over B1-VPG graphs*
• Parameterized complexity of path set packing
• Intersection graphs of maximal sub-polygons of \(k\)-lizards
• Parameterized complexity of path set packing
• Total (restrained) domination in B_k-EPG graphs and B_k-VPG graphs

This page was built for publication: On independent set in \(B_1\)-EPG graphs

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