Geodesic
Structural decomposition of graphs and its application for solving optimization problems on sparse graphs
Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 154-157.

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

The concept of a sparse graph is formalized through a numeric parameter called the treewidth of the graph. This parameter characterizes the size of cliques and separators of the graph. Sparse graphs have small treewidth. A decomposition technique for solving optimization problems on sparse graphs is proposed. This technique implements the principle of “divide and rule” and is based on the atomic representation of the input graph. By an atom of a graph is meant a maximal connected subgraph having no a clique being a minimal separator. An algorithm that creates the atomic representation of the input graph is presented. It is shown that this algorithm for graph $G=(V,E)$ builds the atomic representation in time $\mathrm O(|V|^\tau)$, $2\leq\tau3$. The atomic representation of the graph is a generalization of the decomposition of the graph into blocks using articulation points. If only clique minimum separators are used, then the set of atoms is unique to a given graph. The important properties of atoms are presented. Based on these properties, atomic representation can be used for optimization problems, which are based on the ratio of the adjacency of vertices and edges. For two problems, called All-Pairs Shortest-Path and Maximum-Clique-Problem, the results of the application of atomic representation are presented. It is shown that the time of solving these problems depends linearly on the number of vertices of the input graph. Of course, this is true if the input graph has bounded treewidth. The obtained results make it possible to handle sparse graphs, which have a very large number of vertices. For example, such graphs are Small World Graphs.
Keywords: sparse graph, graph algorithms, treewidth, tree decomposition, atom graph. 
@article{PDMA_2014_7_a65,
     author = {V. V. Bykova},
     title = {Structural decomposition of graphs and its application for solving optimization problems on sparse graphs},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {154--157},
     publisher = {mathdoc},
     number = {7},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a65/}
}
TY  - JOUR
AU  - V. V. Bykova
TI  - Structural decomposition of graphs and its application for solving optimization problems on sparse graphs
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2014
SP  - 154
EP  - 157
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a65/
LA  - ru
ID  - PDMA_2014_7_a65
ER  - 
%0 Journal Article
%A V. V. Bykova
%T Structural decomposition of graphs and its application for solving optimization problems on sparse graphs
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 154-157
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a65/
%G ru
%F PDMA_2014_7_a65
V. V. Bykova. Structural decomposition of graphs and its application for solving optimization problems on sparse graphs. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 154-157. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a65/

[1] Gardiner E., Willett P., Artymiuk P., “Graph-theoretic techniques for macromolecular docking”, J. Chem. Inf. Comput., 40:2 (2000), 273–279 | DOI

[2] Broder A., Kumar R., Maghoul F., et al., “Graph structure in the Web”, Comput. Networks, 33 (2000), 309–320 | DOI

[3] Boginski V., Butenko S., Pardalos P. M., “Mining market data: A network approach”, Comput. Operat. Res., 33:11 (2006), 3171–3184 | DOI | Zbl

[4] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2004

[5] Bykova V. V., “O razlozhenii gipergrafa klikovymi minimalnymi separatorami”, Zhurnal Sibirskogo federalnogo universiteta. Matematika i fizika, 5:1 (2012), 36–45

[6] Bykova V. V., “FPT-algoritmy na grafakh ogranichennoi drevovidnoi shiriny”, Prikladnaya diskretnaya matematika, 2012, no. 2(16), 65–78

[7] Emelichev V. A., Melnikov O. I., Sarvanov V.I., Tyshkevich R. I., Lektsii po teorii grafov, Knizhnyi dom “LIBROKOM”, M., 2012