License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.39
URN: urn:nbn:de:0030-drops-96213
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9621/
Berenger, Cedric ;
Niebert, Peter ;
Perrot, Kevin
Balanced Connected Partitioning of Unweighted Grid Graphs
Abstract
We consider a partitioning problem for grid graphs with special constraints: a (square) grid graph as well as a number of colors is given, a solution is a coloring approximatively assigning the same number of vertices to each color and such that the induced subgraph for each color is connected. In a "rooted" variant, a vertex to be included in the coloring for each color is specified as well. This problem has a concrete motivation in multimedia streaming applications.
We show that the general problem is NP-complete. On the other hand, we define a reasonable easy subclass of grid graphs for which solutions always exist and can be computed by a greedy algorithm.
BibTeX - Entry
@InProceedings{berenger_et_al:LIPIcs:2018:9621,
author = {Cedric Berenger and Peter Niebert and Kevin Perrot},
title = {{Balanced Connected Partitioning of Unweighted Grid Graphs}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {39:1--39:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9621},
URN = {urn:nbn:de:0030-drops-96213},
doi = {10.4230/LIPIcs.MFCS.2018.39},
annote = {Keywords: grid graphs, connected partitioning, NP-completeness, graph algorithm}
}
Keywords: |
|
grid graphs, connected partitioning, NP-completeness, graph algorithm |
Collection: |
|
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
27.08.2018 |