Cover Image

Deterministic Online Bipartite Edge Coloring

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Blikstad, Joakim, Svensson, Ola, Vintan, Radu, Wajc, David
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Edge Coloring: Sharp Thresholds
by: Blikstad, Joakim, et al.
Published: (2025)

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

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

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
by: Blikstad, Joakim, et al.
Published: (2024)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
by: Bernstein, Aaron, et al.
Published: (2024)

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
by: Kuo, Tung-Wei
Published: (2024)

When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching
by: Udwani, Rajan
Published: (2023)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
by: Braverman, Mark, et al.
Published: (2024)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
by: Buchbinder, Niv, et al.
Published: (2025)

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

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Edge-Weighted Online Bipartite Matching
by: Fahrbach, Matthew, et al.
Published: (2020)

Deterministic Dynamic Edge Colouring
by: Christiansen, Aleksander B. G.
Published: (2024)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
by: Ito, Takehiro, et al.
Published: (2025)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Dynamic Edge Coloring of Forests
by: Kaplan, Haim, et al.
Published: (2026)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

Degree-bounded Online Bipartite Matching: OCS vs. Ranking
by: Feng, Yilong, et al.
Published: (2025)

A New Impossibility Result for Online Bipartite Matching Problems
by: Chierichetti, Flavio, et al.
Published: (2025)

Combinatorial Stationary Prophet Inequalities
by: Patel, Neel, et al.
Published: (2023)

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
by: Björklund, Andreas, et al.
Published: (2024)

Dimension-Free Correlated Sampling for the Hypersimplex
by: Joseph, et al.
Published: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk
by: Lin, Honghong, et al.
Published: (2024)

Data-Driven Solution Portfolios
by: Drygala, Marina, et al.
Published: (2024)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
by: Anand, Aditya, et al.
Published: (2024)

Improved Streaming Edge Coloring
by: Chechik, Shiri, et al.
Published: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

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

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

Biclique Reconfiguration in Bipartite Graphs
by: Otachi, Yota, et al.
Published: (2026)

Colorful Vertex Recoloring of Bipartite Graphs
by: Patt-Shamir, Boaz, et al.
Published: (2025)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

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