Article ID Journal Published Year Pages File Type
4647363 Discrete Mathematics 2014 8 Pages PDF
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
, , ,