Computing the map of geometric minimal cuts

DOI10.1007/S00453-012-9704-9MaRDI QIDQ476438zbMATH OpenOpenAlexFDO

Authors Jinhui Xu, Evanthia Papadopoulou, Lei 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

zbMATH Keywords

computational geometryplane sweep algorithmgeometric minimal cutHausdorff Voronoi diagramoutput sensitive algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Computing the Map of Geometric Minimal Cuts
• Map of geometric minimal cuts for general planar embedding
• THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH
• THE L_∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS
• A fast hypergraph min-cut algorithm for circuit partitioning

Cites work

• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• A combinatorial property of convex sets
• A sweepline algorithm for Voronoi diagrams
• Abstract Voronoi diagrams revisited
• Concrete and abstract Voronoi diagrams
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Dynamic fractional cascading
• Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction
• Making data structures persistent
• Near-optimal fully-dynamic graph connectivity
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Randomized incremental construction of abstract Voronoi diagrams
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• Sparsification—a technique for speeding up dynamic graph algorithms
• THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH
• THE L_∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS
• The Hausdorff Voronoi diagram of point clusters in the plane
• The upper envelope of piecewise linear functions: Algorithms and applications
• ``The big sweep: On the power of the wavefront approach to Voronoi diagrams

Cited in

(6)

• Influence-based Voronoi diagrams of clusters
• On clustering induced Voronoi diagrams
• Map of geometric minimal cuts for general planar embedding
• Computing the Map of Geometric Minimal Cuts
• An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces
• The L∞ Hausdorff Voronoi Diagram Revisited

This page was built for publication: Computing the map of geometric minimal cuts

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