Independent set of convex polygons: from n^ to 1+ via shrinking
DOI10.1007/S00453-017-0347-8zbMATH Open1390.68733DBLPjournals/algorithmica/Wiese18OpenAlexW2737247819WikidataQ59528414 ScholiaQ59528414MaRDI QIDQ1742371FDOQ1742371
Authors: Andreas Wiese 
Publication date: 11 April 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0347-8
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
approximation algorithmsconvex polygonsindependent setPTASresource augmentationgeometric intersection graphsshrinking
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)
Cites Work
- Unit disk graphs
- Approximation schemes for covering and packing problems in image processing and VLSI
- Data Mining with optimized two-dimensional association rules
- Independent set of intersection graphs of convex objects in 2D
- A constant factor approximation algorithm for unsplittable flow on paths
- Optimal packing and covering in the plane are NP-complete
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Title not available (Why is that?)
- Fast stabbing of boxes in high dimensions
- Maximum independent set of rectangles
- Computing the independence number of intersection graphs
- Label placement by maximum independent set in rectangles
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Efficient approximation algorithms for tiling and packing problems with rectangles
- Title not available (Why is that?)
- Approximation algorithms for maximum independent set of pseudo-disks
- Constant integrality gap LP formulations of unsplittable flow on a path
- Quasi-polynomial time approximation scheme for sparse subsets of polygons
- A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
- How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
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)
