Restricted space algorithms for isomorphism on bounded treewidth graphs
DOI10.1016/J.IC.2012.05.003zbMATH Open1251.05167OpenAlexW2129003155MaRDI QIDQ714737FDOQ714737
Jacobo Torán, Fabian Wagner, Bireswar Das
Publication date: 11 October 2012
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2012.05.003
Recommendations
- Restricted space algorithms for isomorphism on bounded treewidth graphs
- Canonizing Graphs of Bounded Tree Width in Logspace
- Canonizing graphs of bounded tree width in logspace
- Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
- Isomorphism for graphs of bounded distance width
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- A partial k-arboretum of graphs with bounded treewidth
- Undirected connectivity in log-space
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Isomorphism for graphs of bounded distance width
- Title not available (Why is that?)
- Completeness results for graph isomorphism.
- The Isomorphism Problem for k-Trees Is Complete for Logspace
- Bounded Tree-Width and LOGCFL
- Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
- Title not available (Why is that?)
- Computing LOGCFL certificates
- Testing Graph Isomorphism in Parallel by Playing a Game
Cited In (4)
This page was built for publication: Restricted space algorithms for isomorphism on bounded treewidth graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714737)
