scientific article; zbMATH DE number 4064511

MaRDI QIDQ3798260zbMATH OpenFDO

Authors Ming-Yang Kao

Publication date 1988

zbMATH Keywords

cycle separatordepth-first search forestdeterministic NCparallel computationplanar directed graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parallel Depth-First Search in General Directed Graphs
• An optimal parallel algorithm for planar cycle separators
• A linear-processor algorithm for depth-first search in planar graphs
• Improved parallel depth-first search in undirected planar graphs
• Not all planar digraphs have small cycle separators

Cited in

(7)

• A model classifying algorithms as inherently sequential with applications to graph searching
• Not all planar digraphs have small cycle separators
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• An optimal parallel algorithm for planar cycle separators
• Parallel Depth-First Search in General Directed Graphs
• Improved parallel depth-first search in undirected planar graphs
• Parallel complexity of depth-first-search and maximal path in restricted graph classes

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798260)