DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2018.39

Balanced Connected Partitioning of Unweighted Grid Graphs

Authors: Cedric Berenger, Peter Niebert, and Kevin Perrot

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

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.

Cite as

Cedric Berenger, Peter Niebert, and Kevin Perrot. Balanced Connected Partitioning of Unweighted Grid Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{berenger_et_al:LIPIcs.MFCS.2018.39,
  author =	{Berenger, Cedric and Niebert, Peter and Perrot, Kevin},
  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 =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.39},
  URN =		{urn:nbn:de:0030-drops-96213},
  doi =		{10.4230/LIPIcs.MFCS.2018.39},
  annote =	{Keywords: grid graphs, connected partitioning, NP-completeness, graph algorithm}
}

Document

DOI: 10.4230/DagSemRep.254

Temporal Logics for Distributed Systems - Paradigms and Algorithms (Dagstuhl Seminar 99411)

Authors: Edmund M. Clarke, Ursula Goltz, Peter Niebert, and Wojciech Penczek

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract

Cite as

Edmund M. Clarke, Ursula Goltz, Peter Niebert, and Wojciech Penczek. Temporal Logics for Distributed Systems - Paradigms and Algorithms (Dagstuhl Seminar 99411). Dagstuhl Seminar Report 254, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{clarke_et_al:DagSemRep.254,
  author =	{Clarke, Edmund M. and Goltz, Ursula and Niebert, Peter and Penczek, Wojciech},
  title =	{{Temporal Logics for Distributed Systems - Paradigms and Algorithms (Dagstuhl Seminar 99411)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{254},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.254},
  URN =		{urn:nbn:de:0030-drops-151402},
  doi =		{10.4230/DagSemRep.254},
}

Search Results

Documents authored by Niebert, Peter

Balanced Connected Partitioning of Unweighted Grid Graphs

Abstract

Cite as

Temporal Logics for Distributed Systems - Paradigms and Algorithms (Dagstuhl Seminar 99411)

Abstract

Cite as

Thanks for your feedback!

Could not send message