Isomorphism testing of k-trees is in NC, for fixed k
From MaRDI portal
Publication:910212
DOI10.1016/0020-0190(90)90011-LzbMath0695.68031OpenAlexW1983937448MaRDI QIDQ910212
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
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