Independent set of intersection graphs of convex objects in 2D
From MaRDI portal
Publication:2489017
DOI10.1016/j.comgeo.2005.12.001zbMath1153.68513OpenAlexW2012427196MaRDI QIDQ2489017
Nabil H. Mustafa, Pankaj K. Agarwal
Publication date: 16 May 2006
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2005.12.001
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (29)
Packing and covering with balls on Busemann surfaces ⋮ Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract) ⋮ Optimal space coverage with white convex polygons ⋮ Geometric Hitting Sets for Disks: Theory and Practice ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ Improved results on geometric hitting set problems ⋮ The clique problem in ray intersection graphs ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ On streaming algorithms for geometric independent set and clique ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking ⋮ Matching colored points with rectangles ⋮ Packing and covering with non-piercing regions ⋮ Limits of local search: quality and efficiency ⋮ Unnamed Item ⋮ Planar point sets determine many pairwise crossing segments ⋮ White Space Regions ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the chromatic number of disjointness graphs of curves ⋮ A bipartite analogue of Dilworth's theorem for multiple partial orders ⋮ Simple PTAS's for families of graphs excluding a minor ⋮ A tight analysis of geometric local search ⋮ Stochastic makespan minimization in structured set systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on maximum independent sets in rectangle intersection graphs
- Optimization, approximation, and complexity classes
- On computing the length of longest increasing subsequences
- Label placement by maximum independent set in rectangles
- Some geometric applications of Dilworth's theorem
- Intersection graphs of segments
- Cutting glass
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Algorithmic graph theory and perfect graphs
- A decomposition theorem for partially ordered sets
- Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Decomposable searching problems I. Static-to-dynamic transformation
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- On rectangle intersection and overlap graphs
- Approximating maximum independent sets by excluding subgraphs
This page was built for publication: Independent set of intersection graphs of convex objects in 2D
