Cover Image

Fast algorithms for Vizing's theorem on bounded degree graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bernshteyn, Anton, Dhawan, Abhishek
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
by: Bernshteyn, Anton, et al.
Published: (2024)

Reductions in local certification
by: Esperet, Louis, et al.
Published: (2025)

Scheduled Jacobian Chaining
by: Märtens, Simon, et al.
Published: (2025)

A subquadratic certification scheme for P5-free graphs
by: Bousquet, Nicolas, et al.
Published: (2024)

Borel Vizing's Theorem for Graphs of Subexponential Growth
by: Bernshteyn, Anton, et al.
Published: (2023)

Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation
by: Chang, Yen-Hsiang, et al.
Published: (2025)

Renaming in distributed certification
by: Bousquet, Nicolas, et al.
Published: (2024)

Local certification of forbidden subgraphs
by: Bousquet, Nicolas, et al.
Published: (2024)

Complexity landscape for local certification
by: Bousquet, Nicolas, et al.
Published: (2025)

Local Ratio based Real-time Job Offloading and Resource Allocation in Mobile Edge Computing
by: Gao, Chuanchao, et al.
Published: (2025)

Computing in Anonymous Dynamic Networks Is Linear
by: Di Luna, Giuseppe A., et al.
Published: (2022)

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

Efficient Parallel $(Δ+1)$-Edge-Coloring
by: Elkin, Michael, et al.
Published: (2026)

A Randomised Approach to Distributed Sorting
by: Olesker-Taylor, Sam
Published: (2025)

Model-Agnostic Approximation of Constrained Forest Problems
by: Coupette, Corinna, et al.
Published: (2024)

GenTT: Generate Vectorized Codes for General Tensor Permutation
by: Chen, Yaojian, et al.
Published: (2025)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
by: Izumi, Taisuke, et al.
Published: (2025)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

Near-optimal population protocols on bounded-degree trees
by: Rybicki, Joel, et al.
Published: (2026)

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
by: Cook, Linda, et al.
Published: (2025)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
by: Izumi, Taisuke, et al.
Published: (2023)

Invitation to Local Algorithms
by: Rozhoň, Václav
Published: (2024)

A Cut-Matching Game for Constant-Hop Expanders
by: Haeupler, Bernhard, et al.
Published: (2022)

Optimal local certification on graphs of bounded pathwidth
by: Baterisna, Dan Alden, et al.
Published: (2025)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
by: Alecu, Bogdan, et al.
Published: (2024)

Revising Apetrei's bounding volume hierarchy construction algorithm to allow stackless traversal
by: Prokopenko, Andrey, et al.
Published: (2024)

Moser-Tardos Algorithm with small number of random bits
by: Csóka, Endre, et al.
Published: (2022)

Local certification of geometric graph classes
by: Defrain, Oscar, et al.
Published: (2023)

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)

Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
by: Flin, Maxime, et al.
Published: (2024)

Sharp Online Hardness for Large Balanced Independent Sets
by: Dhawan, Abhishek, et al.
Published: (2025)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
by: d'Orsi, Tommaso, et al.
Published: (2024)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

Parallel Dynamic Maximal Matching
by: Ghaffari, Mohsen, et al.
Published: (2024)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
by: Ghaffari, Mohsen, et al.
Published: (2024)

Fast Deterministic Distributed Degree Splitting
by: Maus, Yannic, et al.
Published: (2026)

Fast Broadcast in Highly Connected Networks
by: Chandra, Shashwat, et al.
Published: (2024)

Fast Concurrent Primitives Despite Contention
by: Bender, Michael A., et al.
Published: (2026)

Binsparse: A Specification for Cross-Platform Storage of Sparse Matrices and Tensors
by: Brock, Benjamin, et al.
Published: (2025)