Theory and application of width bounded geometric separators
From MaRDI portal
Publication:632801
DOI10.1016/j.jcss.2010.05.003zbMath1219.68158OpenAlexW2016458081MaRDI QIDQ632801
Publication date: 28 March 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.05.003
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)
Related Items
Cites Work
- A framework for solving VLSI graph layout problems
- An application of the planar separator theorem to counting problems
- A study on two geometric location problems
- Optimal packing and covering in the plane are NP-complete
- Unit disk graphs
- Exact and approximation algorithms for clustering
- Reduced constants for simple cycle graph separation
- A separator theorem for graphs of bounded genus
- Geometric Separators and Their Applications to Protein Folding in the HP-Model
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Planar Formulae and Their Uses
- On the Problem of Partitioning Planar Graphs
- Planar Separators
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Sublinear Time Width-Bounded Separators and Their Application to the Protein Side-Chain Packing Problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
