Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications (Q6202221): Difference between revisions

Latest revision as of 10:35, 16 December 2024

scientific article; zbMATH DE number 7824310

Language	Label	Description	Also known as
English	Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications	scientific article; zbMATH DE number 7824310

Statements

instance of

scholarly article

0 references

title

Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications (English)

0 references

author

Yi-Jun Chang

0 references

published in

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing

0 references

publication date

26 March 2024

0 references

full work available at URL

https://arxiv.org/abs/2304.04699

0 references

zbMATH Keywords

distributed approximation

0 references

expander decomposition

0 references

property testing

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs

0 references

Distributed Computing

0 references

A Local Constant Factor MDS Approximation for Bounded Genus Graphs

0 references

Distributed Dominating Set Approximations beyond Planar Graphs

0 references

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

0 references

Near-optimal Distributed Triangle Enumeration via Expander Decompositions

0 references

Deterministic coin tossing with applications to optimal parallel list ranking

0 references

Distributed Almost Exact Approximations for Minor-Closed Families

0 references

Fast Distributed Approximations in Planar Graphs

0 references

Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs

0 references

Distributed Strong Diameter Network Decomposition

0 references

Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

0 references

Distributed Algorithms for Planar Networks I

0 references

Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut

0 references

On the complexity of local distributed graph problems

0 references

Distributed MST and Routing in Almost Mixing Time

0 references

Q5090923

0 references

Tight Analyses of Two Local Load Balancing Algorithms

0 references

Round- and Message-Optimal Distributed Graph Algorithms

0 references

Low-Congestion Shortcuts without Embedding

0 references

Near-optimal low-congestion shortcuts on bounded parameter graphs

0 references

Q5090925

0 references

Minor Excluded Network Families Admit Fast Distributed Algorithms

0 references

Excluded minors, network decomposition, and multicommodity flow

0 references

Distributed minimum dominating set approximations in restricted families of graphs

0 references

Leveraging Linial’s Locality Limit

0 references

Property testing of planarity in the \textsf{CONGEST} model

0 references

Planar diameter via metric compression

0 references

Locality in Distributed Graph Algorithms

0 references

Low diameter graph decompositions

0 references

The Power of Distributed Verifiers in Interactive Proofs

0 references

Distributed Computing: A Locality-Sensitive Approach

0 references

Graph minors. XX: Wagner's conjecture

0 references

Polylogarithmic-time deterministic network decomposition and distributed derandomization

0 references

Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs

0 references

The extremal function for complete minors

0 references

A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

0 references

Near-optimal distributed DFS in planar graphs

0 references

Identifiers

arXiv ID

2304.04699

0 references

DOI

10.1145/3583668.3594604

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6202221

@@ Property / OpenAlex ID @@
+W4380880028
@@ Property / OpenAlex ID: W4380880028 / rank @@
+Normal rank
@@ Property / cites work @@
+Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
+Normal rank
@@ Property / cites work @@
+Distributed Computing
@@ Property / cites work: Distributed Computing / rank @@
+Normal rank
@@ Property / cites work @@
+A Local Constant Factor MDS Approximation for Bounded Genus Graphs
+Normal rank
@@ Property / cites work @@
+Distributed Dominating Set Approximations beyond Planar Graphs
+Normal rank
@@ Property / cites work @@
+Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
+Normal rank
@@ Property / cites work @@
+Near-optimal Distributed Triangle Enumeration via Expander Decompositions
+Normal rank
@@ Property / cites work @@
+Deterministic coin tossing with applications to optimal parallel list ranking
+Normal rank
@@ Property / cites work @@
+Distributed Almost Exact Approximations for Minor-Closed Families
+Normal rank
@@ Property / cites work @@
+Fast Distributed Approximations in Planar Graphs
@@ Property / cites work: Fast Distributed Approximations in Planar Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
+Normal rank
@@ Property / cites work @@
+Distributed Strong Diameter Network Decomposition
@@ Property / cites work: Distributed Strong Diameter Network Decomposition / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Distributed Algorithms for Planar Networks I
@@ Property / cites work: Distributed Algorithms for Planar Networks I / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
+Normal rank
@@ Property / cites work @@
+On the complexity of local distributed graph problems
+Normal rank
@@ Property / cites work @@
+Distributed MST and Routing in Almost Mixing Time
@@ Property / cites work: Distributed MST and Routing in Almost Mixing Time / rank @@
+Normal rank
@@ Property / cites work @@
+Q5090923
@@ Property / cites work: Q5090923 / rank @@
+Normal rank
@@ Property / cites work @@
+Tight Analyses of Two Local Load Balancing Algorithms
+Normal rank
@@ Property / cites work @@
+Round- and Message-Optimal Distributed Graph Algorithms
+Normal rank
@@ Property / cites work @@
+Low-Congestion Shortcuts without Embedding
@@ Property / cites work: Low-Congestion Shortcuts without Embedding / rank @@
+Normal rank
@@ Property / cites work @@
+Near-optimal low-congestion shortcuts on bounded parameter graphs
+Normal rank
@@ Property / cites work @@
+Q5090925
@@ Property / cites work: Q5090925 / rank @@
+Normal rank
@@ Property / cites work @@
+Minor Excluded Network Families Admit Fast Distributed Algorithms
+Normal rank
@@ Property / cites work @@
+Excluded minors, network decomposition, and multicommodity flow
+Normal rank
@@ Property / cites work @@
+Distributed minimum dominating set approximations in restricted families of graphs
+Normal rank
@@ Property / cites work @@
+Leveraging Linial’s Locality Limit
@@ Property / cites work: Leveraging Linial’s Locality Limit / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing of planarity in the \textsf{CONGEST} model
+Normal rank
@@ Property / cites work @@
+Planar diameter via metric compression
@@ Property / cites work: Planar diameter via metric compression / rank @@
+Normal rank
@@ Property / cites work @@
+Locality in Distributed Graph Algorithms
@@ Property / cites work: Locality in Distributed Graph Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Low diameter graph decompositions
@@ Property / cites work: Low diameter graph decompositions / rank @@
+Normal rank
@@ Property / cites work @@
+The Power of Distributed Verifiers in Interactive Proofs
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+Graph minors. XX: Wagner's conjecture
@@ Property / cites work: Graph minors. XX: Wagner's conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Polylogarithmic-time deterministic network decomposition and distributed derandomization
+Normal rank
@@ Property / cites work @@
+Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
+Normal rank
@@ Property / cites work @@
+The extremal function for complete minors
@@ Property / cites work: The extremal function for complete minors / rank @@
+Normal rank
@@ Property / cites work @@
+A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
+Normal rank
@@ Property / cites work @@
+Near-optimal distributed DFS in planar graphs
@@ Property / cites work: Near-optimal distributed DFS in planar graphs / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q130816873
@@ Property / Wikidata QID: Q130816873 / rank @@
+Normal rank