Chordal graph recognition is in NC

DOI10.1016/0020-0190(87)90140-2zbMath0653.68035OpenAlexW2110140952MaRDI QIDQ1108003

Anders Edenbrandt

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90140-2

zbMATH Keywords

computational complexityanalysis of algorithmsparallel processingchordal graphNCgraph separator

Mathematics Subject Classification ID

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

Related Items (4)

Minimal triangulations of graphs: a survey ⋮ An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph ⋮ Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs ⋮ Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs

Cites Work

• Unnamed Item
• On rigid circuit graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• An O(logn) parallel connectivity algorithm
• Algorithmic Aspects of Vertex Elimination on Graphs

This page was built for publication: Chordal graph recognition is in NC