Finding minimum-quotient cuts in planar graphs

DOI10.1145/167088.167284zbMath1310.05203OpenAlexW2024654848MaRDI QIDQ5248548

James K. Park, Cynthia A. Phillips

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167284

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Unnamed Item ⋮ Balanced partitions of trees and applications ⋮ Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation

This page was built for publication: Finding minimum-quotient cuts in planar graphs