Log-space algorithms for paths and matchings in \(k\)-trees

DOI10.1007/s00224-013-9469-9zbMath1281.68132OpenAlexW2037858972MaRDI QIDQ385514

Bireswar Das, Prajakta Nimbhorkar, Samir Datta

Publication date: 2 December 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9469-9

zbMATH Keywords

reachabilitymatchingtree-widthlog-space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Bounded Treewidth and Space-Efficient Linear Algebra ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators ⋮ Memory efficient algorithms for cactus graphs and block graphs ⋮ Space complexity of reachability testing in labelled graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Planar and grid graph reachability problems
• Graph minors. III. Planar tree-width
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Counting quantifiers, successor relations, and logarithmic space
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Deterministically isolating a perfect matching in bipartite planar graphs
• Division in logspace-uniformNC¹
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
• Undirected connectivity in log-space
• On the Bipartite Unique Perfect Matching Problem
• Computing Algebraic Formulas Using a Constant Number of Registers
• An Optimal Parallel Algorithm for Formula Evaluation
• Bounded Tree-Width and LOGCFL
• Making Nondeterminism Unambiguous
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• The Space Complexity of k-Tree Isomorphism
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• On acyclic simplicial complexes
• Planarity, Determinants, Permanents, and (Unique) Matchings
• Fast parallel reordering and isomorphism testing of \(k\)-trees

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