Log-space algorithms for paths and matchings in k-trees

DOI10.4230/LIPICS.STACS.2010.2456MaRDI QIDQ3113750zbMATH OpenFDO

Authors Bireswar Das, Samir Datta, Prajakta Nimbhorkar

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_135a.html

zbMATH Keywords

\(k\)-treeslog-spacematchingreachability

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Log-space algorithms for paths and matchings in k-trees
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• The isomorphism problem for \(k\)-trees is complete for logspace
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• STACS 2004

Cited in

(9)

• Balancing bounded treewidth circuits
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
• A Logspace Algorithm for Partial 2-Tree Canonization
• Log-space algorithms for paths and matchings in k-trees
• STACS 2004
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Space Complexity of Reachability Testing in Labelled Graphs
• Reachability in graphs with polynomially many surface non-separating cycles is in UL

This page was built for publication: Log-space algorithms for paths and matchings in \(k\)-trees

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