Theory and application of width bounded geometric separators

DOI10.1016/J.JCSS.2010.05.003MaRDI QIDQ632801zbMATH OpenOpenAlexFDO

Authors Bin Fu

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

zbMATH Keywords

disk coveringdivide and conquerwidth bounded separator

Mathematics Subject Classification ID

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)

Recommendations

• 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

Cites work

• 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

Cited in

(8)

• 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)