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

Please wait, while we are loading the content...

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

Content Provider	Springer Nature Link
Author	Mendez, P. Ossona Nešetřil, J.
Copyright Year	2015
Abstract	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 $$\mathcal {CONGEST}_\mathrm{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.
Ending Page	49
Page Count	11
Starting Page	39
File Format	PDF
ISSN	01782770
e-ISSN	14320452
Journal	Distributed Computing
Issue Number	1
Volume Number	29
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2015-09-07
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computer Systems Organization and Communication Networks Computer Hardware Distributed algorithm Software Engineering/Programming and Operating Systems Graph theory Low tree-depth decomposition Theory of Computation Graph algorithms Distributed algorithms Graph theory (including graph drawing) Coloring of graphs and hypergraphs Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On Low Tree-Depth Decompositions

Distributed deterministic edge coloring using bounded neighborhood independence

Distributed computing with advice: information sensitivity of graph coloring

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

Combinatorial algorithms for distributed graph coloring

Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs

An optimal maximal independent set algorithm for bounded-independence graphs

Path multicoloring with fewer colors in spiders and caterpillars

Drawing Graphs in the Plane with High Resolution

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

Similar Documents

On Low Tree-Depth Decompositions

Distributed deterministic edge coloring using bounded neighborhood independence

Distributed computing with advice: information sensitivity of graph coloring

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

Combinatorial algorithms for distributed graph coloring

Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs

An optimal maximal independent set algorithm for bounded-independence graphs

Path multicoloring with fewer colors in spiders and caterpillars

Drawing Graphs in the Plane with High Resolution

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