Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647363 | Discrete Mathematics | 2014 | 8 Pages |
Abstract
We present a minimal counterexample to an O(|V||E|)O(|V||E|) algorithm for decomposing a graph G=(V,E)G=(V,E) by maximal cliques proposed by R. Tarjan. We also present a modification to this algorithm which is correct while retaining its O(|V||E|)O(|V||E|) complexity.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Márcia R. Cerioli, Hugo Nobrega, Petrucio Viana,