Chordal graph recognition is in NC

DOI10.1016/0020-0190(87)90140-2zbMATH Open0653.68035OpenAlexW2110140952MaRDI QIDQ1108003FDOQ1108003

Authors: 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)

Cites Work

• On rigid circuit graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An O(logn) parallel connectivity algorithm
• Title not available (Why is that?)

Cited In (4)

• An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
• Minimal triangulations of graphs: a survey
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108003)