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

divide and conquerdisk coveringwidth bounded separator

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

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

• 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?)
• A Separator Theorem for Planar Graphs
• A framework for solving VLSI graph layout problems
• A separator theorem for graphs of bounded genus
• 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 Separators and Their Applications to Protein Folding in the HP-Model
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• 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

(6)

• Theory and Application of Width Bounded Geometric Separator
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A PTAS for a disc covering problem using width-bounded separators
• Improved sublinear time algorithm for width-bounded separators
• Computing and Combinatorics
• Balanced line separators of unit disk graphs

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)