Theory and application of width bounded geometric separators
Graph algorithms (graph-theoretic aspects) (05C85) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
In this paper the notion of width bounded geometric separator is presented and techniques for proving the existence of a width bounded separator in any fixed \(d\)-dimensional Euclidean space are developed. The brute-force algorithm of a width bounded geometric separator computation is given. Separators are applied in obtaining \(2^{O(\sqrt n)}\) time exact algorithms for a class of NP-complete geometric problems whose previous algorithms take \(n^{O(\sqrt n)}\) time. One of those problems is the well-known disk covering problem, which seeks to determine the minimal number of fixed-size disks to cover \(n\) points on a plane. They also include some NP-hard problems on disk graphs, such as the maximum independent set problem, the vertex cover problem, and the minimum dominating set problem. For a constant \(a>0\) and a set of points \(Q\) on the plane, an \(a\)-wide separator is the region between two parallel lines of distance \(a\) that partitions \(Q\) into \(Q_{1}\) (on the left side of the region), \(S\) (inside the region), and \(Q_{2}\) (on the right side of the region). If the distance is at least one between every two points in the set \(Q\) with \(n\) points, there is an \(a\)-wide separator that partitions \(Q\) into \(Q_{1}, S\) and \(Q_{2}\) such that \(|Q_{1}|,|Q_{2}| \leqslant (2/3)n\), and \(|S| \leqslant 1.2126a \sqrt n\). The width bounded separator in \(d\)-dimensional Euclidean space with fixed \(d\) is controlled by two parallel hyper-planes, and is used to design \(2^{O(n^{1-\frac 1d})}\)-time algorithms for the \(d\)-dimensional disk covering problem and the above other problems in the \(d\)-dimensional disk graphs. The results of this paper are a generalization and improvement of the results obtained by \textit{B. Fu} and \textit{W. Wang} [SIAM J. Comput. 37, No.~4, 1014--1029 (2007; Zbl 1167.68463)].
- Theory and Application of Width Bounded Geometric Separator
- Improved sublinear time algorithm for width-bounded separators
- Computing and Combinatorics
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- A PTAS for a disc covering problem using width-bounded separators
- A framework for solving VLSI graph layout problems
- A separator theorem for graphs of bounded genus
- A Separator Theorem for Planar Graphs
- A study on two geometric location problems
- An application of the planar separator theorem to counting problems
- Applications of a Planar Separator Theorem
- Approximation schemes for covering and packing problems in image processing and VLSI
- Exact and approximation algorithms for clustering
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Geometric Separators and Their Applications to Protein Folding in the HP-Model
- scientific article; zbMATH DE number 1003278 (Why is no real title available?)
- scientific article; zbMATH DE number 3750313 (Why is no real title available?)
- scientific article; zbMATH DE number 1017008 (Why is no real title available?)
- scientific article; zbMATH DE number 1756013 (Why is no real title available?)
- scientific article; zbMATH DE number 1789934 (Why is no real title available?)
- scientific article; zbMATH DE number 1796976 (Why is no real title available?)
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- On the Problem of Partitioning Planar Graphs
- Optimal packing and covering in the plane are NP-complete
- Planar Formulae and Their Uses
- Planar Separators
- Polynomial-time approximation schemes for geometric graphs
- Reduced constants for simple cycle graph separation
- Sublinear Time Width-Bounded Separators and Their Application to the Protein Side-Chain Packing Problem
- Unit disk graphs
- A PTAS for a disc covering problem using width-bounded separators
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- Improved sublinear time algorithm for width-bounded separators
- Theory and Application of Width Bounded Geometric Separator
- Computing and Combinatorics
- Balanced line separators of unit disk graphs
- A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)
- A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)
This page was built for publication: Theory and application of width bounded geometric separators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q632801)
