Independent set of convex polygons: from n^ to 1+ via shrinking

DOI10.1007/S00453-017-0347-8MaRDI QIDQ1742371zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andreas Wiese

Publication date 11 April 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-017-0347-8

zbMATH Keywords

approximation algorithmsconvex polygonsindependent setPTASresource augmentationgeometric intersection graphsshrinking

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Independent Set of Convex Polygons: from \(n^{\epsilon }\) to \(1+\epsilon\) via shrinking
• Approximation schemes for independent set and sparse subsets of polygons
• Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• Algorithm Theory - SWAT 2004

Cites work

• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• scientific article; zbMATH DE number 1424295 (Why is no real title available?)
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• A constant factor approximation algorithm for unsplittable flow on paths
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation schemes for covering and packing problems in image processing and VLSI
• Computing the independence number of intersection graphs
• Constant integrality gap LP formulations of unsplittable flow on a path
• Data Mining with optimized two-dimensional association rules
• Efficient approximation algorithms for tiling and packing problems with rectangles
• Fast stabbing of boxes in high dimensions
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
• Independent set of intersection graphs of convex objects in 2D
• Label placement by maximum independent set in rectangles
• Maximum independent set of rectangles
• Optimal packing and covering in the plane are NP-complete
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• Unit disk graphs

Cited in

(5)

• Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
• Independent Set of Convex Polygons: from \(n^{\epsilon }\) to \(1+\epsilon\) via shrinking
• Approximation schemes for independent set and sparse subsets of polygons
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices

This page was built for publication: Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking

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