A linear-processor algorithm for depth-first search in planar graphs (Q1110342): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / OpenAlex ID
 
Property / OpenAlex ID: W2170132497 / rank
 
Normal rank

Revision as of 21:27, 19 March 2024

scientific article
Language Label Description Also known as
English
A linear-processor algorithm for depth-first search in planar graphs
scientific article

    Statements

    A linear-processor algorithm for depth-first search in planar graphs (English)
    0 references
    0 references
    1988
    0 references
    We present an n-processor and \(O(\log^ 2 n)\) time parallel RAM algorithm for finding a depth-first-search tree in an n-vertex planar graph. The algorithm is based on a new n-processor algorithm for finding a cyclic separator in a planar graph and Smith's [\textit{J. R. Smith}, SIAM J. Comput. 15, 814-830 (1986; Zbl 0612.68059)] original parallel depth- first-search algorithm for planar graphs.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    parallel algorithm
    0 references
    cyclic separator
    0 references
    depth-first-search
    0 references
    planar graphs
    0 references
    0 references