Isomorphism Testing in Hookup Classes

DOI10.1137/0603025MaRDI QIDQ3968949zbMATH OpenOpenAlexFDO

Authors Andrzej Proskurowski, Maria M. Klawe, Derek G. Corneil

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

graph isomorphismNP-completek-treeshookup classes

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99)

Cites work

• scientific article; zbMATH DE number 3651075 (Why is no real title available?)
• scientific article; zbMATH DE number 3679848 (Why is no real title available?)
• Incidence matrices and interval graphs
• Networks immune to isolated failures
• On simple characterizations of k-trees
• The graph isomorphism disease

Cited in

(13)

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

This page was built for publication: Isomorphism Testing in Hookup Classes

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