Log-space algorithms for paths and matchings in \(k\)-trees
type: Item
instance of: scholarly article
title: Log-space algorithms for paths and matchings in \(k\)-trees
zbMATH Open document ID: 1281.68132
author: Bireswar Das
author: Samir Datta
author: Prajakta Nimbhorkar
published in: Theory of Computing Systems
publication date: 2013-12-02T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 6235175
zbMATH Keywords: tree-width
zbMATH Keywords: log-space
zbMATH Keywords: reachability
zbMATH Keywords: matching
MaRDI profile type: Publication
full work available at URL: s00224-013-9469-9
OpenAlex ID: W2037858972
cites work: Planar and grid graph reachability problems
cites work: The Space Complexity of k-Tree Isomorphism
cites work: Computing Algebraic Formulas Using a Constant Number of Registers
cites work: Q3219133
cites work: An Optimal Parallel Algorithm for Formula Evaluation
cites work: Division in logspace-uniform NC
cites work: On acyclic simplicial complexes
cites work: Planarity, Determinants, Permanents, and (Unique) Matchings
cites work: Deterministically isolating a perfect matching in bipartite planar graphs
cites work: Counting quantifiers, successor relations, and logarithmic space
cites work: On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
cites work: Fast parallel reordering and isomorphism testing of \(k\)-trees
cites work: Embeddings of \(k\)-connected graphs of pathwidth \(k\)
cites work: Uniform constant-depth threshold circuits for division and iterated multiplication.
cites work: On the Bipartite Unique Perfect Matching Problem
cites work: Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
cites work: Constructing a perfect matching is in random NC
cites work: The Isomorphism Problem for k-Trees Is Complete for Logspace
cites work: Q5414582
cites work: Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
cites work: Matching is as easy as matrix inversion
cites work: Undirected connectivity in log-space
cites work: Making Nondeterminism Unambiguous
cites work: Graph minors. III. Planar tree-width
cites work: Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
cites work: Bounded Tree-Width and LOGCFL
DOI: 10.1007/S00224-013-9469-9
Recommended article: Q3113750
Recommended article: An efficient algorithm for some tree matching problems
Recommended article: Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
Recommended article: Polynomial time algorithms for variants of graph matching on partial \(k\)-trees
Recommended article: Logspace optimization problems and their approximability properties
Recommended article: Fundamentals of Computation Theory
Recommended article: Exact and approximate algorithms for unordered tree matching
Recommended article: Paths, trees and matchings under disjunctive constraints
Recommended article: Q4263472
Recommended article: On the \(K\) shortest path trees problem
description: scientific article; zbMATH DE number 6235175