The k-separator problem

Walid Ben-Ameur; Mohamed Ahmed Mohamed-Sidi; José Neto

doi:10.1007/978-3-642-38768-5_31

The k-separator problem

Walid Ben-Ameur, Mohamed Ahmed Mohamed-Sidi, José Neto

CNRS SAMOVAR UMR 5157

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 ₂-free, (G ₁, G ₂, G ₃, P ₆)-free, interval-filament, asteroidal triple-free, weakly chordal, interval and circular-arc graphs. Approximation algorithms are also presented.

Original language	English
Title of host publication	Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
Pages	337-348
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-38768-5_31
Publication status	Published - 8 Oct 2013
Externally published	Yes
Event	19th International Computing and Combinatorics Conference, COCOON 2013 - Hangzhou, China Duration: 21 Jun 2013 → 21 Jun 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7936 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Computing and Combinatorics Conference, COCOON 2013
Country/Territory	China
City	Hangzhou
Period	21/06/13 → 21/06/13

Keywords

approximation algorithms
communication networks
complexity theory
graph partitioning
optimization

Access to Document

10.1007/978-3-642-38768-5_31

Cite this

Ben-Ameur, W., Mohamed-Sidi, M. A., & Neto, J. (2013). The k-separator problem. In Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings (pp. 337-348). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7936 LNCS). https://doi.org/10.1007/978-3-642-38768-5_31

@inproceedings{ee0656a43cf3474e98a3808cf9163c3e,

title = "The k-separator problem",

abstract = "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.",

keywords = "approximation algorithms, communication networks, complexity theory, graph partitioning, optimization",

author = "Walid Ben-Ameur and Mohamed-Sidi, \{Mohamed Ahmed\} and Jos{\'e} Neto",

year = "2013",

month = oct,

day = "8",

doi = "10.1007/978-3-642-38768-5\_31",

language = "English",

isbn = "9783642387678",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "337--348",

booktitle = "Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings",

note = "19th International Computing and Combinatorics Conference, COCOON 2013 ; Conference date: 21-06-2013 Through 21-06-2013",

}

Ben-Ameur, W, Mohamed-Sidi, MA & Neto, J 2013, The k-separator problem. in Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7936 LNCS, pp. 337-348, 19th International Computing and Combinatorics Conference, COCOON 2013, Hangzhou, China, 21/06/13. https://doi.org/10.1007/978-3-642-38768-5_31

The k-separator problem. / Ben-Ameur, Walid; Mohamed-Sidi, Mohamed Ahmed; Neto, José.
Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings. 2013. p. 337-348 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7936 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

The k-separator problem

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this