Independent set of intersection graphs of convex objects in 2D
From MaRDI portal
Publication:2489017
DOI10.1016/J.COMGEO.2005.12.001zbMATH Open1153.68513OpenAlexW2012427196MaRDI QIDQ2489017FDOQ2489017
Authors: 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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Algorithmic graph theory and perfect graphs
- Title not available (Why is that?)
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- Intersection graphs of segments
- On computing the length of longest increasing subsequences
- A decomposition theorem for partially ordered sets
- Decomposable searching problems I. Static-to-dynamic transformation
- Title not available (Why is that?)
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Polynomial-time approximation schemes for packing and piercing fat objects
- Label placement by maximum independent set in rectangles
- Some geometric applications of Dilworth's theorem
- Efficient approximation algorithms for tiling and packing problems with rectangles
- A note on maximum independent sets in rectangle intersection graphs
- On rectangle intersection and overlap graphs
- Title not available (Why is that?)
- Polynomial-time approximation schemes for geometric graphs
- Cutting glass
- Approximating maximum independent sets by excluding subgraphs
Cited In (37)
- Maximum bipartite subgraphs of geometric intersection graphs
- Stochastic makespan minimization in structured set systems (extended abstract)
- Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Improved results on geometric hitting set problems
- A tight analysis of geometric local search
- Stochastic makespan minimization in structured set systems
- Computing the independence number of intersection graphs
- Maximum independent set in 2-direction outersegment graphs
- Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
- Packing and covering with non-piercing regions
- The clique problem in ray intersection graphs
- Algorithm Theory - SWAT 2004
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- A note on maximum independent sets in rectangle intersection graphs
- Optimal space coverage with white convex polygons
- Geometric hitting sets for disks: theory and practice
- Simple PTAS's for families of graphs excluding a minor
- Approximation algorithms for maximum independent set of pseudo-disks
- Planar point sets determine many pairwise crossing segments
- Title not available (Why is that?)
- A bipartite analogue of Dilworth's theorem for multiple partial orders
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- Optimality of geometric local search
- On the size of outer-string representations
- Packing and covering with balls on Busemann surfaces
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- Practical and efficient algorithms for the geometric hitting set problem
- On the chromatic number of disjointness graphs of curves
- White space regions
- Matching colored points with rectangles
- A survey on variant domination problems in geometric intersection graphs
- Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
- On streaming algorithms for geometric independent set and clique
- Limits of local search: quality and efficiency
- Computing maximum independent set on outerstring graphs and their relatives
This page was built for publication: Independent set of intersection graphs of convex objects in 2D
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489017)
