Finding Separator Cuts in Planar Graphs within Twice the Optimal

DOI10.1137/S0097539794271692zbMath0943.68077OpenAlexW2132987209MaRDI QIDQ4268875

Vijay V. Vazirani, Naveen Garg, Huzur Saran

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

planar graphsapproximation algorithmsseparators

Mathematics Subject Classification ID

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

Related Items

A quality and distance guided hybrid algorithm for the vertex separator problem ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem ⋮ The vertex separator problem: a polyhedral investigation ⋮ Balanced cut approximation in random geometric graphs