Isomorphism testing of k-trees is in NC, for fixed k

DOI10.1016/0020-0190(90)90011-LzbMath0695.68031OpenAlexW1983937448MaRDI QIDQ910212

N. Chandrasekharan

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90011-l

zbMATH Keywords

computational complexityparallel algorithmsisomorphismCRCW PRAMk- trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The Space Complexity of k-Tree Isomorphism

Cites Work

• Unnamed Item
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On simple characterizations of k-trees
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Isomorphism Testing in Hookup Classes
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• On acyclic simplicial complexes
• Properties and characterizations of k ‐trees