Image de couverture de livre

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Davies-Peck, Peter
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
par: Kolmogorov, Vladimir, et autres
Publié: (2026)

Parameterized Algorithms for Minimum Sum Vertex Cover
par: Aute, Shubhada, et autres
Publié: (2024)

Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model
par: Robinson, Peter, et autres
Publié: (2025)

New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs
par: Heck, Sophia, et autres
Publié: (2026)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
par: D'Angelo, Gianlorenzo, et autres
Publié: (2025)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
par: Kobayashi, Yusuke, et autres
Publié: (2026)

Approximately: Independence Implies Vertex Cover
par: Har-Peled, Sariel
Publié: (2023)

Approximating Maximum Matching Requires Almost Quadratic Time
par: Behnezhad, Soheil, et autres
Publié: (2024)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
par: Ahi, Mridul, et autres
Publié: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
par: Zheng, Da Wei, et autres
Publié: (2023)

Enumeration kernels for Vertex Cover and Feedback Vertex Set
par: Bougeret, Marin, et autres
Publié: (2025)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
par: Kaul, Matthias, et autres
Publié: (2025)

Expander Decomposition for Non-Uniform Vertex Measures
par: Agassy, Daniel, et autres
Publié: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
par: DeHaan, Ian, et autres
Publié: (2024)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
par: Bhore, Sujoy, et autres
Publié: (2024)

Capacitated Partition Vertex Cover and Partition Edge Cover
par: Dabas, Rajni, et autres
Publié: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
par: Brand, Jan van den, et autres
Publié: (2026)

Weighted Partition Vertex and Edge Cover
par: Dabas, Rajni, et autres
Publié: (2025)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
par: Akhtar, Sheikh Shakil, et autres
Publié: (2025)

Width Parameters for Minimum Flow Decomposition
par: Grigorjew, Andreas, et autres
Publié: (2024)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
par: Mahabadi, Sepideh, et autres
Publié: (2025)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
par: Gupta, Sushmita, et autres
Publié: (2024)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
par: Saito, Rin, et autres
Publié: (2025)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
par: Chuzhoy, Julia, et autres
Publié: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
par: Solomon, Shay, et autres
Publié: (2023)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
par: Kwok, Shawxing
Publié: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
par: Chuzhoy, Julia, et autres
Publié: (2025)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
par: Li, Xizhe, et autres
Publié: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
par: Bentert, Matthias, et autres
Publié: (2025)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
par: Hua, Kevin, et autres
Publié: (2024)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
par: Hamm, Thekla, et autres
Publié: (2022)

Cluster Vertex Deletion on Chordal Graphs
par: Cao, Yixin, et autres
Publié: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
par: Bentert, Matthias, et autres
Publié: (2024)

A Fully-dynamic Approximation Algorithm for Maximum Weight b-Matchings in Graphs
par: Brandt-Tumescheit, Fabian, et autres
Publié: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
par: Jiang, Yonggang, et autres
Publié: (2025)

FPT Approximations for Connected Maximum Coverage
par: Inamdar, Tanmay, et autres
Publié: (2026)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
par: Dong, Sally, et autres
Publié: (2023)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
par: Çivril, Ali
Publié: (2024)

The Power of Greedy for Online Minimum Cost Matching on the Line
par: Balkanski, Eric, et autres
Publié: (2022)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
par: Fischer, Manuela, et autres
Publié: (2021)