A distributed low tree-depth decomposition algorithm for bounded expansion classes

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10333121" target="_blank" >RIV/00216208:11320/16:10333121 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/s00446-015-0251-x" target="_blank" >http://dx.doi.org/10.1007/s00446-015-0251-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00446-015-0251-x" target="_blank" >10.1007/s00446-015-0251-x</a>

Result language

angličtina

Original language name

A distributed low tree-depth decomposition algorithm for bounded expansion classes

Original language description

We study the distributed low tree-depth decomposition problem for graphs restricted to a bounded expansion class. Low tree-depth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a linear-time model checking algorithm for graphs in a bounded expansion class. Recall that bounded expansion classes cover classes of graphs of bounded degree, of planar graphs, of graphs of bounded genus, of graphs of bounded treewidth, of graphs that exclude a fixed minor, and many other graphs. There is a sequential algorithm to compute low tree-depth decomposition (with bounded number of colors) in linear time. In this paper, we give the first efficient distributed algorithm for this problem. As it is usual for a symmetry breaking problem, we consider a synchronous model, and as we are interested in a deterministic algorithm, we use the usual assumption that each vertex has a distinct identity number. We consider the distributed message-passing CONGEST BC model, in which messages have logarithmic length and only local broadcast are allowed. In this model, we present a logarithmic time distributed algorithm for computing a low tree-depth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low tree-depth decomposition linear time algorithm are used as a core procedure in several non-trivial linear time algorithms. We believe that, similarly, low tree-depth decomposition could be at the heart of several non-trivial logarithmic time algorithms.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Distributed Computing

ISSN

0178-2770

e-ISSN

—

Volume of the periodical

29

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

11

Pages from-to

39-49

UT code for WoS article

000374458500003

EID of the result in the Scopus database

2-s2.0-84957851651