Cover Image

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bernstein, Aaron, Chen, Jiale
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Matching Composition and Efficient Weight Reduction in Dynamic Matching
by: Bernstein, Aaron, et al.
Published: (2024)

A Weighted-to-Unweighted Reduction for Matroid Intersection
by: Dudeja, Aditi, et al.
Published: (2026)

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

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
by: Bernstein, Aaron, et al.
Published: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

Efficient Kernelization Algorithm for Bipartite Graph Matching
by: Wu, Guang, et al.
Published: (2024)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
by: Azarmehr, Amir, et al.
Published: (2024)

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

Entropy Regularization and Faster Decremental Matching in General Graphs
by: Chen, Jiale, et al.
Published: (2023)

Revoke vs. Restart in Unweighted Throughput Scheduling
by: He, Changdao
Published: (2025)

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

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2025)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

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

Optimal Rounding for Two-Stage Bipartite Matching
by: Pollner, Tristan, et al.
Published: (2025)

Interval-Constrained Bipartite Matching over Time
by: Abels, Andreas, et al.
Published: (2024)

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

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

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
by: Nägele, Martin, et al.
Published: (2026)

Approximate Bipartite $b$-Matching using Multiplicative Auction
by: Samineni, Bhargav, et al.
Published: (2024)

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

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

Low Sensitivity Hopsets
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

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

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
by: Gharan, Shayan Oveis, et al.
Published: (2025)

Closing the Gap Between Directed Hopsets and Shortcut Sets
by: Bernstein, Aaron, et al.
Published: (2022)

Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
by: Zhang, Yexin, et al.
Published: (2025)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
by: Bai, Xingjian, et al.
Published: (2024)

Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
by: Björklund, Andreas, et al.
Published: (2023)

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)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs
by: Cai, Xinwei, et al.
Published: (2023)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

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