Decomposition by maxclique separators

Authors	M.R. Cerioli H. Nobrega P. Viana
Publication date	2014
Journal	Discrete mathematics
Volume | Issue number	337
Pages (from-to)	119-126
Organisations	Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract	We present a minimal counterexample to an O(|V||E|) algorithm for decomposing a graph 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|) complexity.
Document type	Article
Language	English
Published at	https://doi.org/10.1016/j.disc.2014.07.020
Permalink to this page