Name
Abstract | ||
|---|---|---|
In this paper we consider the problem of computing a map of geometric minimal cuts (called MGMC problem) induced by a planar
rectilinear embedding of a subgraph H = (V
H
, E
H
) of an input graph G. We first show that unlike the classic min-cut problem on graphs, the number of all rectilinear geometric minimal cuts is
bounded by a low polynomial, O(n
3). Our algorithm for identifying geometric minimum cuts runs in O(n
3 logn (loglogn)3) time in the worst case which can be reduced to O(n logn (loglogn)3) when the maximum size of the cut is bounded by a constant, where n = |V
H
|. Once geometric minimal cuts are identified we show that the problem can be reduced to computing the L
∞ Hausdorff Voronoi diagram of axis aligned rectangles. We present the first output-sensitive algorithm to compute this diagram
which runs in O((N + K)log2
N loglogN) time and O(Nlog2
N) space, where N is the number of rectangles and K is the complexity of the diagram.
|
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-10631-6_26 | Algorithmica |
Keywords | Field | DocType |
Geometric minimal cut,Hausdorff Voronoi diagram,Output sensitive algorithm,Plane sweep algorithm,Computational geometry | Discrete mathematics,Combinatorics,Polynomial,Computational geometry,Diagram,Hausdorff space,Voronoi diagram,Output-sensitive algorithm,Sweep line algorithm,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
68 | 4 | 0302-9743 |
Citations | PageRank | References |
3 | 0.44 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jinhui Xu | 1 | 665 | 78.86 |
| Lei Xu | 2 | 154 | 21.38 |
| Evanthia Papadopoulou | 3 | 110 | 18.37 |