Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs

DOI10.1007/978-3-540-77050-3_18MaRDI QIDQ5458836zbMATH OpenOpenAlexFDO

Authors Andreas Jakoby, Till Tantau

Publication date 24 April 2008

Published in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77050-3_18

zbMATH Keywords

logspace algorithmsbounded tree-widthlongest path problemSeries-parallel graphsdistance problem\(K _{4}\)-minor-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1689046
• Parallel algorithms for series parallel graphs and graphs with treewidth two
• Space efficient algorithms for directed series–parallel graphs
• Log-space algorithms for paths and matchings in \(k\)-trees
• Log-space algorithms for paths and matchings in k-trees

Cites work

• scientific article; zbMATH DE number 1754588 (Why is no real title available?)
• scientific article; zbMATH DE number 2086628 (Why is no real title available?)
• An Optimal Parallel Algorithm for Formula Evaluation
• Bounded Tree-Width and LOGCFL
• Computing Algebraic Formulas Using a Constant Number of Registers
• Directed planar reachability is in unambiguous log-space
• Division in logspace-uniform NC
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Parallel algorithms for series parallel graphs and graphs with treewidth two
• Parallel recognition and decomposition of two terminal series parallel graphs
• Parallel recognition of series-parallel graphs
• Planar and grid graph reachability problems
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Space efficient algorithms for directed series–parallel graphs
• The Complexity of Finding Paths in Graphs with Bounded Independence Number
• The Recognition of Series Parallel Digraphs
• Topology of series-parallel networks
• Treewidth: Characterizations, Applications, and Computations
• Two Applications of Inductive Counting for Complementation Problems
• Undirected ST-connectivity in log-space

Cited in

(13)

• Planar and grid graph reachability problems
• scientific article; zbMATH DE number 2086628 (Why is no real title available?)
• Longest paths in planar DAGs in unambiguous log-space
• Complexity of regular functions
• scientific article; zbMATH DE number 1689046 (Why is no real title available?)
• STACS 2004
• Series parallel digraphs with loops
• Space efficient algorithms for directed series–parallel graphs
• Log-space algorithms for paths and matchings in \(k\)-trees
• Log-space algorithms for paths and matchings in \(k\)-trees
• Cross-series-parallel digraphs
• Space efficient algorithm for solving reachability using tree decomposition and separators
• Memory efficient algorithms for cactus graphs and block graphs

This page was built for publication: Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs

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