Parallel complexity of depth-first-search and maximal path in restricted graph classes
From MaRDI portal
Cites work
- A linear-processor algorithm for depth-first search in planar graphs
- A parallel algorithm for the maximal path problem
- A random NC algorithm for depth first search
- Bounded treewidth and space-efficient linear algebra
- Compressed Decision Problems in Hyperbolic Groups.
- Computational Complexity
- Constructing a perfect matching is in random NC
- Depth-first search in directed planar graphs, revisited
- Depth-first search is inherently sequential
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- Directed planar reachability is in unambiguous log-space
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Embedding and canonizing graphs of bounded genus in logspace
- Embeddings of graphs with no short noncontractible cycles
- Extending planar graph algorithms to \(K_{3,3}\)-free graphs
- Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
- Finding small simple cycle separators for 2-connected planar graphs
- Flows in one-crossing-minor-free graphs
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Graph minors. XX: Wagner's conjecture
- Graph Structure Theory
- Graphs on surfaces
- Green's theorem and isolation in planar graphs
- scientific article; zbMATH DE number 4064511 (Why is no real title available?)
- scientific article; zbMATH DE number 45125 (Why is no real title available?)
- Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
- Logspace versions of the theorems of Bodlaender and Courcelle
- Matching is as easy as matrix inversion
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- On the ordered conjecture
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- Parallel Depth-First Search in General Directed Graphs
- Parallelism and the maximal path problem
- Parameterized algorithms
- Planar Depth-First Search in O(\log n) Parallel Time
- Planar graph isomorphism is in log-space
- Planar Strong Connectivity Helps in Parallel Depth-First Search
- Planarity testing revisited
- Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
- Separation of vertices by a circuit
- Space complexity of perfect matching in bounded genus bipartite graphs
- The complexity of planarity testing
- The Even-Path problem in directed single-crossing-minor-free graphs
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Undirected connectivity in log-space
- Zur allgemeinen Kurventheorie.
- Über eine Eigenschaft der ebenen Komplexe
This page was built for publication: Parallel complexity of depth-first-search and maximal path in restricted graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7391895)
