TY - GEN
T1 - The k-separator problem
AU - Ben-Ameur, Walid
AU - Mohamed-Sidi, Mohamed Ahmed
AU - Neto, José
PY - 2013/10/8
Y1 - 2013/10/8
N2 - Given a vertex-weighted undirected graph G = (V,E,w) 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. We show that this problem can be solved in polynomial time for some graph classes: for cycles and trees by a dynamic programming approach and by using a peculiar graph transformation coupled with recent results from the literature for m K 2-free, (G 1, G 2, G 3, P 6)-free, interval-filament, asteroidal triple-free, weakly chordal, interval and circular-arc graphs. Approximation algorithms are also presented.
AB - Given a vertex-weighted undirected graph G = (V,E,w) 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. We show that this problem can be solved in polynomial time for some graph classes: for cycles and trees by a dynamic programming approach and by using a peculiar graph transformation coupled with recent results from the literature for m K 2-free, (G 1, G 2, G 3, P 6)-free, interval-filament, asteroidal triple-free, weakly chordal, interval and circular-arc graphs. Approximation algorithms are also presented.
KW - approximation algorithms
KW - communication networks
KW - complexity theory
KW - graph partitioning
KW - optimization
U2 - 10.1007/978-3-642-38768-5_31
DO - 10.1007/978-3-642-38768-5_31
M3 - Conference contribution
AN - SCOPUS:84884963073
SN - 9783642387678
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 337
EP - 348
BT - Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
T2 - 19th International Computing and Combinatorics Conference, COCOON 2013
Y2 - 21 June 2013 through 21 June 2013
ER -