ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Shortest noncrossing paths in plane graphs (1996)

Takahashi, Junya ; Suzuki, Hitoshi ; Nishizeki, Takao

Springer

Algorithmica 16 (1996), S. 339-357

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Noncrossing paths ; Shortest path ; Plane graphs ; Single-layer routing ; VLSI

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk “noncrossing paths” inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01955681

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit