Theory and application of width bounded geometric separators

DOI10.1016/J.JCSS.2010.05.003zbMATH Open1219.68158OpenAlexW2016458081MaRDI QIDQ632801FDOQ632801

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

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

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)

Cites Work

• Applications of a Planar Separator Theorem
• Unit disk graphs
• Planar Formulae and Their Uses
• Title not available (Why is that?)
• A Separator Theorem for Planar Graphs
• Exact and approximation algorithms for clustering
• Approximation schemes for covering and packing problems in image processing and VLSI
• On the Problem of Partitioning Planar Graphs
• Title not available (Why is that?)
• A framework for solving VLSI graph layout problems
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A study on two geometric location problems
• Optimal packing and covering in the plane are NP-complete
• A separator theorem for graphs of bounded genus
• Planar Separators
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Title not available (Why is that?)
• An application of the planar separator theorem to counting problems
• Reduced constants for simple cycle graph separation
• Polynomial-time approximation schemes for geometric graphs
• Geometric Separators and Their Applications to Protein Folding in the HP-Model
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sublinear Time Width-Bounded Separators and Their Application to the Protein Side-Chain Packing Problem

Cited In (3)

• A PTAS for a disc covering problem using width-bounded separators
• Computing and Combinatorics
• A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection 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)