Computing the map of geometric minimal cuts
DOI10.1007/s00453-012-9704-9zbMath1303.05202OpenAlexW2059004575MaRDI QIDQ476438
Evanthia Papadopoulou, Lei Xu, Jinhui Xu
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9704-9
computational geometryplane sweep algorithmgeometric minimal cutHausdorff Voronoi diagramoutput sensitive algorithm
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Cites Work
- Unnamed Item
- Randomized incremental construction of abstract Voronoi diagrams
- Abstract Voronoi diagrams revisited
- Dynamic fractional cascading
- The upper envelope of piecewise linear functions: Algorithms and applications
- A sweepline algorithm for Voronoi diagrams
- Making data structures persistent
- Concrete and abstract Voronoi diagrams
- A combinatorial property of convex sets
- The Hausdorff Voronoi diagram of point clusters in the plane
- ``The big sweep: On the power of the wavefront approach to Voronoi diagrams
- Near-optimal fully-dynamic graph connectivity
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Sampling to provide or to bound: With applications to fully dynamic graph algorithms
- Sparsification—a technique for speeding up dynamic graph algorithms
- THE L∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS
- Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH