Finding Separator Cuts in Planar Graphs within Twice the Optimal

DOI10.1137/S0097539794271692MaRDI QIDQ4268875zbMATH OpenOpenAlexFDO

Authors Naveen Garg, Huzur Saran, Vijay V. Vazirani

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794271692

zbMATH Keywords

approximation algorithmsplanar graphsseparators

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Combinatorial optimization (90C27)

Recommendations

• A polynomial-time bicriteria approximation scheme for planar bisection
• Partitioning planar graphs with vertex costs: Algorithms and applications
• Weighted graph separators and their applications
• scientific article; zbMATH DE number 867693
• Fast Approximate Graph Partitioning Algorithms

Cited in

(10)

• Balanced cut approximation in random geometric graphs
• A quality and distance guided hybrid algorithm for the vertex separator problem
• Separating double rays in locally finite planar graphs
• Corner cuts are close to optimal: from solid grids to polygons and back
• The vertex separator problem: a polyhedral investigation
• Graph bisection with Pareto optimization
• Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
• Space complexity of optimization problems in planar graphs
• Spectral partitioning works: planar graphs and finite element meshes

This page was built for publication: Finding Separator Cuts in Planar Graphs within Twice the Optimal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268875)