Autor(es)

Moura, Phablo F. S. ; Ota, Matheus Jun ; Wakabayashi, Yoshiko

• Tipo de documento: Artigo Científico
• Fonte: ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2022; v. 13179, p. 13-pg., 2022-01-01.

Resumo

For a given integer k >= 2, partitioning a connected graph into k vertex-disjoint connected subgraphs of similar (or fixed) orders is a classical problem that has been intensively investigated since late seventies. A connected k-partition of a graph is a partition of its vertex set into classes such that each one induces a connected subgraph. Given a connected graph G = (V, E) and a weight function w : V -> Q >=, the balanced connected k-partition problem looks for a connected k-partition of G into classes of roughly the same weight. To model this concept of balance, we seek connected k-partitions that either maximize the weight of a lightest class (MAX-MIN BCPk) or minimize the weight of a heaviest class (MIN-MAX BCPk). These problems, known to be NP-hard, are equivalent only when k/2. We present a simple pseudo-polynomial k/2-approximation algorithm for MIN-MAX BCPk that runs in time O(W vertical bar V vertical bar vertical bar E vertical bar), where W = Sigma(v is an element of V) w(v); then, using a scaling technique, we obtain a (polynomial) (k/2 + epsilon)-approximation with running-time O(vertical bar V vertical bar(3)vertical bar E vertical bar/epsilon), for any fixed epsilon > 0. Additionally, we propose a fixed-parameter tractable algorithm for the unweighted MAX-MIN BCP (where k is part of the input) parameterized by the size of a vertex cover. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático