A polynomial-time OPT^-approximation algorithm for maximum independent set of connected subgraphs in a planar graph

DOI10.1137/1.9781611977912.23MaRDI QIDQ6645368zbMATH OpenFDO

Authors Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki

Publication date 28 November 2024

Full work available at URL https://doi.org/10.1137/1.9781611977912.23

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(4)

• Approximating the maximum independent set of convex polygons with a bounded number of directions
• Parameterized approximation for maximum weight independent set of rectangles and segments
• Random-order online independent set of intervals and hyperrectangles
• Dynamic streaming algorithms for geometric independent set

This page was built for publication: A polynomial-time \(\mathrm{OPT}^\varepsilon\)-approximation algorithm for maximum independent set of connected subgraphs in a planar graph

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