Buchumschlag

Arboricity-Dependent Algorithms for Edge Coloring

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhattacharya, Sayan, Costa, Martín, Panski, Nadav, Solomon, Shay
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

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

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

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Fast Algorithms for Graph Arboricity and Related Problems
von: Cen, Ruoxu, et al.
Veröffentlicht: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
von: Solomon, Shay, et al.
Veröffentlicht: (2023)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
von: Bishnu, Arijit, et al.
Veröffentlicht: (2025)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
von: Dai, Jiangqi, et al.
Veröffentlicht: (2025)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
von: de Vos, Tijn, et al.
Veröffentlicht: (2024)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
von: Bukov, Anton, et al.
Veröffentlicht: (2023)

A Lossless Deamortization for Dynamic Greedy Set Cover
von: Solomon, Shay, et al.
Veröffentlicht: (2024)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
von: Assadi, Sepehr
Veröffentlicht: (2024)

Tree-Like Shortcuttings of Trees
von: Le, Hung, et al.
Veröffentlicht: (2025)

Connectivity Labeling in Faulty Colored Graphs
von: Petruschka, Asaf, et al.
Veröffentlicht: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2026)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Fully Dynamic Euclidean k-Means
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Chasing Positive Bodies
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Approximate Light Spanners in Planar Graphs
von: Le, Hung, et al.
Veröffentlicht: (2025)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
von: Blikstad, Joakim, et al.
Veröffentlicht: (2026)

Dynamic Edge Coloring of Forests
von: Kaplan, Haim, et al.
Veröffentlicht: (2026)

Improved Streaming Edge Coloring
von: Chechik, Shiri, et al.
Veröffentlicht: (2025)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Online Edge Coloring: Sharp Thresholds
von: Blikstad, Joakim, et al.
Veröffentlicht: (2025)

Faster Edge Coloring by Partition Sieving
von: Akmal, Shyan, et al.
Veröffentlicht: (2025)

Deterministic Online Bipartite Edge Coloring
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Engineering Edge Orientation Algorithms
von: Reinstädtler, H., et al.
Veröffentlicht: (2024)

Overlapping and Robust Edge-Colored Clustering in Hypergraphs
von: Crane, Alex, et al.
Veröffentlicht: (2023)

Streaming Edge Coloring with Subquadratic Palette Size
von: Chechik, Shiri, et al.
Veröffentlicht: (2023)