Parallelism and the maximal path problem

Richard Anderson, Ernst W. Mayr

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

22 Zitate (Scopus)

Abstract

The maximal path problem is the following: Given a graph G = (V, E) and a vertex r, find a path starting at r that cannot be extended without encountering a node that is already on the path. We shall show that if all nodes have degree at most D(n), the problem can be solved in O(D(n) log3 n) time using O(n2) processors. We also obtain an NC algorithm for the maximal path problem in planar graphs. Finally, we show that the problem of computing the lexicographically minimal maximal path is P-complete, even when restricted to planar graphs.

OriginalspracheEnglisch
Seiten (von - bis)121-126
Seitenumfang6
FachzeitschriftInformation Processing Letters
Jahrgang24
Ausgabenummer2
DOIs
PublikationsstatusVeröffentlicht - 30 Jan. 1987
Extern publiziertJa

Fingerprint

Untersuchen Sie die Forschungsthemen von „Parallelism and the maximal path problem“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren