ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

Algorithms for multicommodity flows in planar graphs (1989)

Suzuki, Hitoshi ; Nishizeki, Takao ; Saito, Nobuji

Springer

Algorithmica 4 (1989), S. 471-501

zur Merkliste hinzufügen auf der Merkliste

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

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer