A distributed low tree-depth decomposition algorithm for bounded expansion classes
From MaRDI portal
Publication:5964897
DOI10.1007/s00446-015-0251-xzbMath1352.68283OpenAlexW1456870675MaRDI QIDQ5964897
Jaroslav Nešetřil, Patrice 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
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Best monotone degree conditions for graph properties: a survey
- How many \(F\)'s are there in \(G\)?
- Characterisations and examples of graph classes with bounded expansion
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Generalization of transitive fraternal augmentations for directed graphs and its applications
- Colouring graphs with bounded generalized colouring number
- Parallel \((\Delta +1)\)-coloring of constant-degree graphs
- Optimal node ranking of tree in linear time
- Constant-factor approximation of the domination number in sparse graphs
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Tree-depth, subgraph coloring and homomorphism bounds
- Kernelization Using Structural Parameters on Sparse Graph Classes
- A Dynamic Data Structure for MSO Properties in Graphs with Bounded Tree-Depth
- Linear time low tree-width partitions and algorithmic consequences
- Enumeration of monadic second-order queries on trees
- On first-order definable colorings
- The Grad of a Graph and Classes with Bounded Expansion
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- Locality in Distributed Graph Algorithms
- Rankings of Graphs
- Distributed Computing: A Locality-Sensitive Approach
- Deciding First-Order Properties of Nowhere Dense Graphs
- On the complexity of distributed graph coloring
- Locality based graph coloring
- Testing first-order properties for subclasses of sparse graphs
- Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
- Algorithms for Classes of Graphs with Bounded Expansion
This page was built for publication: A distributed low tree-depth decomposition algorithm for bounded expansion classes
