A Logspace Algorithm for Partial 2-Tree Canonization

DOI10.1007/978-3-540-79709-8_8MaRDI QIDQ3503623zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Bireswar Das, Johannes Köbler

Publication date 5 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79709-8_8

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Canonizing graphs of bounded tree width in logspace
• Canonizing Graphs of Bounded Tree Width in Logspace
• scientific article; zbMATH DE number 1088188
• Log-space algorithms for paths and matchings in \(k\)-trees
• Log-space algorithms for paths and matchings in k-trees
• Canonical representations of partial 2-and 3-trees
• Canonical representations of partial 2- and 3-trees
• Fundamentals of Computation Theory
• Logspace optimization problems and their approximability properties
• Computing the maximal canonical form for trees in polynomial time

Cites work

• Canonical representations of partial 2- and 3-trees
• Completeness results for graph isomorphism.
• Group-theoretic algorithms and graph isomorphism
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1091108 (Why is no real title available?)
• scientific article; zbMATH DE number 2086628 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On acyclic simplicial complexes
• Random Graph Isomorphism
• Relationships among $PL$, $\#L$, and the determinant
• Testing Graph Isomorphism in Parallel by Playing a Game
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• The Space Complexity of k-Tree Isomorphism
• Treewidth. Computations and approximations
• Undirected ST-connectivity in log-space

Cited in

(9)

• Canonical representations of partial 2- and 3-trees
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• A note on integral generalized flows in directed partial 2-trees
• Graphs of bounded treewidth can be canonized in AC^1
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• scientific article; zbMATH DE number 1088188 (Why is no real title available?)
• Canonizing graphs of bounded tree width in logspace
• The isomorphism problem for \(k\)-trees is complete for logspace
• A computational approach to construct a multivariate complete graph invariant

This page was built for publication: A Logspace Algorithm for Partial 2-Tree Canonization

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