Isomorphism Testing in Hookup Classes

DOI10.1137/0603025zbMath0503.05023OpenAlexW2001435631MaRDI QIDQ3968949

Andrzej Proskurowski, Derek Gordon Corneil, Maria M. Klawe

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0603025

zbMATH Keywords

NP-completegraph isomorphismk-treeshookup classes

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99)

Related Items

Isomorphism of chordal (6, 3) graphs ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ A fast parallel algorithm to recognize P4-sparse graphs ⋮ On the structure of graphs with few \(P_4\)s ⋮ On the isomorphism of graphs with few P4s ⋮ A Dynamic Programming Approach to the Dominating Set Problem on k-Trees ⋮ Directed path graph isomorphism ⋮ Complement reducible graphs ⋮ Isomorphism testing of k-trees is in NC, for fixed k ⋮ The Space Complexity of k-Tree Isomorphism ⋮ The isomorphism problem for classes of graphs closed under contraction ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Graph reconstruction from unlabeled edge lengths

Cites Work

• On simple characterizations of k-trees
• Incidence matrices and interval graphs
• Networks immune to isolated failures
• The graph isomorphism disease
• Unnamed Item
• Unnamed Item