RUS  ENG
Full version
JOURNALS // Journal of Siberian Federal University. Mathematics & Physics // Archive

J. Sib. Fed. Univ. Math. Phys., 2012 Volume 5, Issue 1, Pages 36–45 (Mi jsfu217)

This article is cited in 2 papers

The clique minimal separator decomposition of a hypergraph

Valentina V. Bykova

Institute of Mathematics, Siberian Federal University, Krasnoyarsk, Russia

Abstract: We present the decomposition of a hypergraph into its atoms with using the clique minimal separators. We have indicated that this decomposition is unique. We offer effective procedures for computing the clique minimal separators and construction the decomposition. We give the application by decomposition for computing the treewidth of a hypergraph.

Keywords: atom hypergraph, clique separator, acyclicity, treewidth.

UDC: 519.1

Received: 18.09.2011
Received in revised form: 25.10.2011
Accepted: 10.11.2011



© Steklov Math. Inst. of RAS, 2024