Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Finding a Region with the Minimum Total L 1 Distance from Prescribed Terminals
    Springer
    Algorithmica 35 (NaN), S. 225-256 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Facility location, Optimal region, Rectilinear shortest path, L1 distance.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Given k terminals and n axis-parallel rectangular obstacles on the plane, our algorithm finds a plane region R * such that, for any point p in R * , the total length of the k shortest rectilinear paths connecting p and the k terminals without passing through any obstacle is minimum. The algorithm is output-sensitive, and takes O((K+n) log n) time and O(K+n) space if k is a fixed constant, where K is the total number of polygonal vertices of the found region R * .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s00453-002-0997-y
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Algorithms for multicommodity flows in planar graphs (1989)
    Springer
    Algorithmica 4 (1989), S. 471-501 
    Details
    ISSN: 1432-0541
    Keywords: Algorithm ; Cut condition ; Muiticommodity flow ; Network ; Planar graph ; Shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper gives efficient algorithms for the muiticommodity flow problem for two classes C12 and C01 of planar undirected graphs. Every graph in C12 has two face boundaries B1 and B2 such that each of the source-sink pairs lies on B1 or B2. On the other hand, every graph inC 01 has a face boundaryB 1 such that some of the source-sink pairs lie onB 1 and all the other pairs share a common sink lying onB 1. The algorithms run inO(kn +nT(n)) time if a graph hasn vertices andk source-sink pairs andT(n) is the time required for finding the single-source shortest paths in a planar graph ofn vertices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553903
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Editors' foreword (1993)
    Springer
    Algorithmica 9 (1993), S. 517-517 
    Details
    ISSN: 1432-0541
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190152
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Shortest noncrossing paths in plane graphs (1996)
    Springer
    Algorithmica 16 (1996), S. 339-357 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Drawing plane graphs nicely (1985)
    Springer
    Acta informatica 22 (1985), S. 187-201 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph “convex” if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, produces a pleasing drawing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00264230
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Book
    Book
    Planar graphs: theory and algorithms; 140 (1988)
    Amsterdam u.a. :North-Holland,
    Details
    Title: Planar graphs: theory and algorithms; 140
    Author: Nishizeki, Takao
    Contributer: Chiba, Norishige
    Publisher: Amsterdam u.a. :North-Holland,
    Year of publication: 1988
    Pages: 232 S.
    Series Statement: North-Holland mathematics studies 140
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...