Geodesic
The clique minimal separator decomposition of a~hypergraph
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 5 (2012) no. 1, pp. 36-45.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{JSFU_2012_5_1_a3,
     author = {Valentina V. Bykova},
     title = {The clique minimal separator decomposition of a~hypergraph},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {36--45},
     publisher = {mathdoc},
     volume = {5},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2012_5_1_a3/}
}
TY  - JOUR
AU  - Valentina V. Bykova
TI  - The clique minimal separator decomposition of a~hypergraph
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2012
SP  - 36
EP  - 45
VL  - 5
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2012_5_1_a3/
LA  - ru
ID  - JSFU_2012_5_1_a3
ER  - 
%0 Journal Article
%A Valentina V. Bykova
%T The clique minimal separator decomposition of a~hypergraph
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2012
%P 36-45
%V 5
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2012_5_1_a3/
%G ru
%F JSFU_2012_5_1_a3
Valentina V. Bykova. The clique minimal separator decomposition of a~hypergraph. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 5 (2012) no. 1, pp. 36-45. http://geodesic.mathdoc.fr/item/JSFU_2012_5_1_a3/

[1] R. E. Tarjan, “Decomposition by clique separators”, Discrete Mathematics, 55 (1985), 221–232 | DOI | MR | Zbl

[2] H. G. Leimer, “Optimal decomposition by clique separators”, Discrete Mathematics, 113 (1993), 99–123 | DOI | MR | Zbl

[3] B. Kaba, N. Pinet, G. Lelandais, A. Sigayret, A. Berry, “Clustering gene expression data using graph separators”, In Silico Biology, 7 (2007), 433–452

[4] M. Didi Biha, B. Kaba, M. J. Meurs, E. SanJuan, “Graph decomposition approaches for terminology graphs”, Proc. MICAI, 2007, 883–893

[5] H. L. Bodlaender, “Discovering treewidth”, Proc. of the 31st Conference SOFSEM 2005, Lecture Notes in Computer Science, 3381, Springer-Verlag, 2005, 1–16 | MR | Zbl

[6] A. A. Zykov, “Gipergrafy”, UMN, 29:6 (1974), 89–154 | MR | Zbl

[7] V. V. Bykova, “M-atsiklicheskie i drevovidnye gipergrafy”, Izv. Tomskogo politekhn. un-ta. Matematika i mekhanika. Fizika, 317:2 (2010), 25–30

[8] G. A. Dirac, “On rigid circuit graphs”, Abh. Math. Sem. Univ. Hamburg, 25 (1961), 71–76 | DOI | MR | Zbl

[9] A. Berry, J. P. Bordat, P. Heggernes, G. Simonet, Y. Villanger, “A wide range algorithm for minimal triangulation from an arbitrary ordering”, J. Algorithms, 58:1 (2006), 33–66 | DOI | MR | Zbl

[10] D. J. Rose, R. E. Tarjan, G. S. Lueker, “Algorithmic aspects of vertex elimination on graphs”, SIAM J. Comput., 5 (1976), 266–283 | DOI | MR | Zbl

[11] A. Berry, J. R. S. Blair, P. Heggernes, “Maximum cardinality search for computing minimal triangulations of graphs”, Algorithmica, 39 (2004), 287–298 | DOI | MR | Zbl

[12] V. V. Bykova, “Rekurrentnye metody vychisleniya drevovidnoi shiriny gipergrafa”, Izv. Tomskogo politekhn. un-ta. Upravlenie, vych. tekhnika i informatika, 318:5 (2011), 5–10