NC algorithms for recognizing chordal graphs and k trees

DOI10.1109/12.5979zbMath0658.68080OpenAlexW2141173730MaRDI QIDQ3806839

N. Chandrasekharan, S. Sitharama Iyengar

Publication date: 1988

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/2278ebad0cc0e3f9fd96d277903ce2c5e53c3c1b

zbMATH Keywords

parallel algorithmstreeschordal graphsNC algorithm

Mathematics Subject Classification ID

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

Related Items (7)

Minimal triangulations of graphs: a survey ⋮ An nc algorithm to recognize hhd-free graphs ⋮ A fast parallel algorithm to recognize partitionable graphs ⋮ The Space Complexity of k-Tree Isomorphism ⋮ Complexity of some graph-based bounds on the probability of a union of events ⋮ On the complexity of some subgraph problems ⋮ The Impact of Locality in the Broadcast Congested Clique Model

This page was built for publication: NC algorithms for recognizing chordal graphs and k trees