Chordal graph recognition is in NC
From MaRDI portal
Publication:1108003
DOI10.1016/0020-0190(87)90140-2zbMath0653.68035MaRDI QIDQ1108003
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
computational complexity; analysis of algorithms; parallel processing; chordal graph; NC; graph separator
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Minimal triangulations of graphs: a survey, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
Cites Work