Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
  • 1
    Digitale Medien
    Digitale Medien
    Shortest noncrossing paths in plane graphs (1996)
    Springer
    Algorithmica 16 (1996), S. 339-357 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Noncrossing paths ; Shortest path ; Plane graphs ; Single-layer routing ; VLSI
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01955681
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    Finding a Region with the Minimum Total L 1 Distance from Prescribed Terminals
    Springer
    Algorithmica 35 (NaN), S. 225-256 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Key words. Facility location, Optimal region, Rectilinear shortest path, L1 distance.
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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 * .
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/s00453-002-0997-y
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    Algorithms for multicommodity flows in planar graphs (1989)
    Springer
    Algorithmica 4 (1989), S. 471-501 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Algorithm ; Cut condition ; Muiticommodity flow ; Network ; Planar graph ; Shortest path
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01553903
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    Editors' foreword (1993)
    Springer
    Algorithmica 9 (1993), S. 517-517 
    Details
    ISSN: 1432-0541
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01190152
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    Drawing plane graphs nicely (1985)
    Springer
    Acta informatica 22 (1985), S. 187-201 
    Details
    ISSN: 1432-0525
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF00264230
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...