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

DOI10.1007/978-3-540-77050-3_18zbMath1135.68518OpenAlexW1537214435MaRDI QIDQ5458836

Till Tantau, Andreas Jakoby

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 theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Series parallel digraphs with loops ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ Complexity of regular functions ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators ⋮ Cross-series-parallel digraphs ⋮ Memory efficient algorithms for cactus graphs and block graphs ⋮ Planar and grid graph reachability problems

Cites Work

• Unnamed Item
• Unnamed Item
• Planar and grid graph reachability problems
• Parallel recognition and decomposition of two terminal series parallel graphs
• Parallel recognition of series-parallel graphs
• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Topology of series-parallel networks
• Division in logspace-uniformNC¹
• Directed Planar Reachability Is in Unambiguous Log-Space
• Treewidth: Characterizations, Applications, and Computations
• Undirected ST-connectivity in log-space
• Two Applications of Inductive Counting for Complementation Problems
• The Recognition of Series Parallel Digraphs
• Computing Algebraic Formulas Using a Constant Number of Registers
• An Optimal Parallel Algorithm for Formula Evaluation
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Bounded Tree-Width and LOGCFL
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• The Complexity of Finding Paths in Graphs with Bounded Independence Number
• Space efficient algorithms for directed series–parallel graphs
• Parallel algorithms for series parallel graphs and graphs with treewidth two

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