Geodesic
Solving the weighted $k$-separator problem in graphs with specific modules
Trudy Instituta matematiki, Tome 24 (2016) no. 1, pp. 61-74.

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

Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{R}^+$ and a positive integer $k,$ we consider the $k$-separator problem: it consists in finding a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to $k.$ Using the notion of modular decomposition we extend the class of graphs on which this problem can be solved in polynomial time. For a graph $G$ that is modular decomposable into $\pi(G)\subseteq\{P_4,\ldots,P_m\}\cup\{C_5,\ldots,C_m\}$ we give an $O(n^2)$ algorithm for finding the minimum weight of $k$-separators. The algorithm solves this problem for cographs in time $O(n).$ Moreover, we give an $O(n)$ time algorithm solving this problem for the series-parallel graphs. 
@article{TIMB_2016_24_1_a8,
     author = {V. V. Lepin},
     title = {Solving the weighted $k$-separator problem in graphs with specific modules},
     journal = {Trudy Instituta matematiki},
     pages = {61--74},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2016_24_1_a8/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - Solving the weighted $k$-separator problem in graphs with specific modules
JO  - Trudy Instituta matematiki
PY  - 2016
SP  - 61
EP  - 74
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2016_24_1_a8/
LA  - ru
ID  - TIMB_2016_24_1_a8
ER  - 
%0 Journal Article
%A V. V. Lepin
%T Solving the weighted $k$-separator problem in graphs with specific modules
%J Trudy Instituta matematiki
%D 2016
%P 61-74
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2016_24_1_a8/
%G ru
%F TIMB_2016_24_1_a8
V. V. Lepin. Solving the weighted $k$-separator problem in graphs with specific modules. Trudy Instituta matematiki, Tome 24 (2016) no. 1, pp. 61-74. http://geodesic.mathdoc.fr/item/TIMB_2016_24_1_a8/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp.

[2] Ben-Ameur W., Mohamed-Sidi M., Neto J., “The $k$-Separator Problem”, COCOON 2013, LNCS, 7936, 337–348 | Zbl

[3] Ben-Ameur W., Mohamed-Sidi M., Neto J., “The $k$-separator problem: polyhedra, complexity and approximation results”, J. Comb. Optim., 29 (2015), 276–307 | DOI | Zbl

[4] Boliac R., Cameron K., Lozin V. V., “On computing the dissociation number and the induced matching number of bipartite graphs”, Ars Comb., 72 (2004), 241–253 | Zbl

[5] Gallai T., “Transitiv orienterbare graphe”, Acta Math. Acad. Sci. Hungar., 18 (1967), 25–66 | DOI | Zbl

[6] James L. O., Stanton R. G., Cowan D. D., “Graph decomposition for undirected graphs”, Proc. of the third Southeastern International Conference on Combinatorics, Graph Theory, and Computing, CGTC'72, 1972, 281–290 | Zbl

[7] Cournier A., Habib M., “A New Linear Algorithm for Modular Decomposition”, Proc. of Trees in Algebra and Programming, CAAP'94, LNCS, 787, 1994, 68–84 | Zbl

[8] McConnell R. M., Spinrad J. P., “Modular decomposition and transitive orientation”, Discr. Math., 201 (1999), 189–241 | DOI | Zbl

[9] Tedder M., Corneil D., Habib M., Paul C., “Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations”, Proc. Int. Colloq. Automata, Languages and Programming, ICALP 2008, Lecture Notes in Computer Science, 5125, Springer-Verlag, 2008, 634–645 | DOI | Zbl

[10] Valdes J., Tarjan R. E., Lawler E. L., “The recognition of series parallel digraphs”, SIAM J. Comput., 11 (1982), 298–313 | DOI | Zbl