Balanced Connected Partitioning of Unweighted Grid Graphs

Authors Cedric Berenger, Peter Niebert, Kevin Perrot



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.39.pdf
  • Filesize: 1.02 MB
  • 18 pages

Document Identifiers

Author Details

Cedric Berenger
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
Peter Niebert
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
Kevin Perrot
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.MFCS.2018.39

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Hardware → Partitioning and floorplanning
Keywords
  • grid graphs
  • connected partitioning
  • NP-completeness
  • graph algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail