TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

NP-completeness results for partitioning a graph into total dominating sets

Tutkimustuotosvertaisarvioitu

Standard

NP-completeness results for partitioning a graph into total dominating sets. / Koivisto, Mikko; Laakkonen, Petteri; Lauri, Juho.

julkaisussa: Theoretical Computer Science, 01.01.2018.

Tutkimustuotosvertaisarvioitu

Harvard

APA

Koivisto, M., Laakkonen, P., & Lauri, J. (2018). NP-completeness results for partitioning a graph into total dominating sets. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2018.04.006

Vancouver

Koivisto M, Laakkonen P, Lauri J. NP-completeness results for partitioning a graph into total dominating sets. Theoretical Computer Science. 2018 tammi 1. https://doi.org/10.1016/j.tcs.2018.04.006

Author

Koivisto, Mikko ; Laakkonen, Petteri ; Lauri, Juho. / NP-completeness results for partitioning a graph into total dominating sets. Julkaisussa: Theoretical Computer Science. 2018.

Bibtex - Lataa

@article{cccfcaeb6aaf4d02a2b0018a030c633b,
title = "NP-completeness results for partitioning a graph into total dominating sets",
abstract = "A total domatic k-partition of a graph is a partition of its vertex set into k subsets such that each intersects the open neighborhood of each vertex. The maximum k for which a total domatic k-partition exists is known as the total domatic number of a graph G, denoted by dt(G). We extend considerably the known hardness results by showing it is[Formula presented]-complete to decide whether dt(G)≥3 where G is a bipartite planar graph of bounded maximum degree. Similarly, for every k≥3, it is[Formula presented]-complete to decide whether dt(G)≥k, where G is split or k-regular. In particular, these results complement recent combinatorial results regarding dt(G) on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general n-vertex graphs, we show the problem is solvable in 2nnO(1) time, and derive even faster algorithms for special graph classes.",
keywords = "Combinatorics, Computational complexity, Graph theory, Total domatic number",
author = "Mikko Koivisto and Petteri Laakkonen and Juho Lauri",
year = "2018",
month = "1",
day = "1",
doi = "10.1016/j.tcs.2018.04.006",
language = "English",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS (suitable for import to EndNote) - Lataa

TY - JOUR

T1 - NP-completeness results for partitioning a graph into total dominating sets

AU - Koivisto, Mikko

AU - Laakkonen, Petteri

AU - Lauri, Juho

PY - 2018/1/1

Y1 - 2018/1/1

N2 - A total domatic k-partition of a graph is a partition of its vertex set into k subsets such that each intersects the open neighborhood of each vertex. The maximum k for which a total domatic k-partition exists is known as the total domatic number of a graph G, denoted by dt(G). We extend considerably the known hardness results by showing it is[Formula presented]-complete to decide whether dt(G)≥3 where G is a bipartite planar graph of bounded maximum degree. Similarly, for every k≥3, it is[Formula presented]-complete to decide whether dt(G)≥k, where G is split or k-regular. In particular, these results complement recent combinatorial results regarding dt(G) on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general n-vertex graphs, we show the problem is solvable in 2nnO(1) time, and derive even faster algorithms for special graph classes.

AB - A total domatic k-partition of a graph is a partition of its vertex set into k subsets such that each intersects the open neighborhood of each vertex. The maximum k for which a total domatic k-partition exists is known as the total domatic number of a graph G, denoted by dt(G). We extend considerably the known hardness results by showing it is[Formula presented]-complete to decide whether dt(G)≥3 where G is a bipartite planar graph of bounded maximum degree. Similarly, for every k≥3, it is[Formula presented]-complete to decide whether dt(G)≥k, where G is split or k-regular. In particular, these results complement recent combinatorial results regarding dt(G) on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general n-vertex graphs, we show the problem is solvable in 2nnO(1) time, and derive even faster algorithms for special graph classes.

KW - Combinatorics

KW - Computational complexity

KW - Graph theory

KW - Total domatic number

U2 - 10.1016/j.tcs.2018.04.006

DO - 10.1016/j.tcs.2018.04.006

M3 - Article

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -