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

DOI10.1007/S00446-015-0251-XMaRDI QIDQ5964897zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. Ossona de Mendez

Publication date 1 March 2016

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-015-0251-x

zbMATH Keywords

distributed algorithmgraph theorylow tree-depth decomposition

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Linear time low tree-width partitions and algorithmic consequences
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Treedepth bounds in linear colorings
• Grad and classes with bounded expansion. I: Decompositions
• Polynomial treedepth bounds in linear colorings

Cites work

• A dynamic data structure for MSO properties in graphs with bounded tree-depth
• Algorithms for classes of graphs with bounded expansion
• Best monotone degree conditions for graph properties: a survey
• Characterisations and examples of graph classes with bounded expansion
• Colouring graphs with bounded generalized colouring number
• Constant-factor approximation of the domination number in sparse graphs
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed computing through combinatorial topology
• Distributed Computing: A Locality-Sensitive Approach
• Enumeration of monadic second-order queries on trees
• Generalization of transitive fraternal augmentations for directed graphs and its applications
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• How many F's are there in G?
• scientific article; zbMATH DE number 1414315 (Why is no real title available?)
• Kernelization using structural parameters on sparse graph classes
• Linear time low tree-width partitions and algorithmic consequences
• Locality based graph coloring
• Locality in Distributed Graph Algorithms
• Methods for algorithmic meta theorems
• Minimum dominating set approximation in graphs of bounded arboricity
• On first-order definable colorings
• On the complexity of distributed graph coloring
• Optimal node ranking of tree in linear time
• Parallel \((\Delta +1)\)-coloring of constant-degree graphs
• Rankings of Graphs
• Sparsity. Graphs, structures, and algorithms
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Testing first-order properties for subclasses of sparse graphs
• The Grad of a Graph and Classes with Bounded Expansion
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(4)

• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• Distributed model checking on graphs of bounded treedepth
• Computing treedepth in polynomial space and linear FPT time
• Brief announcement: Distributed model checking on graphs of bounded treedepth

This page was built for publication: A distributed low tree-depth decomposition algorithm for bounded expansion classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964897)