Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs

DOI10.1007/3-540-45071-8_7zbMATH Open1276.05117OpenAlexW1761251274MaRDI QIDQ3082912FDOQ3082912

Authors: Martin Wahlen, Andrzej Lingas 

Publication date: 18 March 2011

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

Full work available at URL: https://doi.org/10.1007/3-540-45071-8_7

Recommendations

• A note on maximum independent set and related problems on box graphs
• Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs
• Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs

zbMATH Keywords

maximum independent setminimum vertex coverbox graphmaximum induced subgraphorthogonal rectangles

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75)

Cited In (6)

• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• A note on maximum independent set and related problems on box graphs
• Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs

This page was built for publication: Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs

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