Imagen de Portada

On the Complexity of Distributed Edge Coloring and Orientation Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Brandt, Sebastian, Kuhn, Fabian, Parsaeian, Zahra
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Massively Parallel Ruling Set Made Deterministic
por: Giliberti, Jeff, et al.
Publicado: (2024)

Laminar Matroid Secretary: Greedy Strikes Back
por: Huang, Zhiyi, et al.
Publicado: (2023)

Engineering Edge Orientation Algorithms
por: Reinstädtler, H., et al.
Publicado: (2024)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
por: Ghaffari, Mohsen, et al.
Publicado: (2026)

Deterministic Edge Coloring with few Colors in CONGEST
por: Blikstad, Joakim, et al.
Publicado: (2026)

Faster Distributed $Δ$-Coloring via Ruling Subgraphs
por: Bourreau, Yann, et al.
Publicado: (2025)

Faster Distributed $Δ$-Coloring via a Reduction to MIS
por: Bourreau, Yann, et al.
Publicado: (2025)

Improved Streaming Edge Coloring
por: Chechik, Shiri, et al.
Publicado: (2025)

Dynamic Edge Coloring of Forests
por: Kaplan, Haim, et al.
Publicado: (2026)

EF(X) Orientations: A Parameterized Complexity Perspective
por: Kanellopoulos, Sotiris, et al.
Publicado: (2025)

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
por: Großmann, Ernestine, et al.
Publicado: (2024)

Online Edge Coloring: Sharp Thresholds
por: Blikstad, Joakim, et al.
Publicado: (2025)

Faster Edge Coloring by Partition Sieving
por: Akmal, Shyan, et al.
Publicado: (2025)

Deterministic Online Bipartite Edge Coloring
por: Blikstad, Joakim, et al.
Publicado: (2024)

Arboricity-Dependent Algorithms for Edge Coloring
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Overlapping and Robust Edge-Colored Clustering in Hypergraphs
por: Crane, Alex, et al.
Publicado: (2023)

Streaming Edge Coloring with Subquadratic Palette Size
por: Chechik, Shiri, et al.
Publicado: (2023)

Online Edge Coloring is (Nearly) as Easy as Offline
por: Blikstad, Joakim, et al.
Publicado: (2024)

Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
por: Fuchs, Marc, et al.
Publicado: (2024)

On the Node-Averaged Complexity of Locally Checkable Problems on Trees
por: Balliu, Alkida, et al.
Publicado: (2023)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
por: Assadi, Sepehr
Publicado: (2024)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
por: Sadeh, Yaniv, et al.
Publicado: (2026)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
por: El-Hayek, Antoine, et al.
Publicado: (2023)

On the Complexity of Secluded Path Problems
por: Hanaka, Tesshu, et al.
Publicado: (2026)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
por: Elkin, Michael, et al.
Publicado: (2024)

A Near-Optimal Kernel for a Coloring Problem
por: Haviv, Ishay, et al.
Publicado: (2025)

Towards Settling the Complexity of the Lettericity Problem
por: Grobler, Mario, et al.
Publicado: (2026)

Computational Complexity of the Interval Ordering Problem
por: Pawlowski, Simeon, et al.
Publicado: (2026)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Towards Optimal Distributed Edge Coloring with Fewer Colors
por: Jakob, Manuel, et al.
Publicado: (2025)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

Algorithms and Complexity of Hedge Cluster Deletion Problems
por: Konstantinidis, Athanasios L., et al.
Publicado: (2025)

Query Complexity of the Metric Steiner Tree Problem
por: Chen, Yu, et al.
Publicado: (2022)

Complexity Classes for Online Problems with and without Predictions
por: Berg, Magnus, et al.
Publicado: (2024)

The Parameterized Complexity Landscape of the Unsplittable Flow Problem
por: Ganian, Robert, et al.
Publicado: (2024)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
por: Aute, Shubhada, et al.
Publicado: (2026)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

Tree Coloring: Random Order and Predictions
por: Frei, Fabian, et al.
Publicado: (2024)