Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | Davies-Peck, Peter |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| 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)
par: Kolmogorov, Vladimir, et autres
Publié: (2026)
Parameterized Algorithms for Minimum Sum Vertex Cover
par: Aute, Shubhada, et autres
Publié: (2024)
par: Aute, Shubhada, et autres
Publié: (2024)
Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model
par: Robinson, Peter, et autres
Publié: (2025)
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)
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)
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)
par: Kobayashi, Yusuke, et autres
Publié: (2026)
Approximately: Independence Implies Vertex Cover
par: Har-Peled, Sariel
Publié: (2023)
par: Har-Peled, Sariel
Publié: (2023)
Approximating Maximum Matching Requires Almost Quadratic Time
par: Behnezhad, Soheil, et autres
Publié: (2024)
par: Behnezhad, Soheil, et autres
Publié: (2024)
Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
par: Ahi, Mridul, et autres
Publié: (2025)
par: Ahi, Mridul, et autres
Publié: (2025)
Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
par: Zheng, Da Wei, et autres
Publié: (2023)
par: Zheng, Da Wei, et autres
Publié: (2023)
Enumeration kernels for Vertex Cover and Feedback Vertex Set
par: Bougeret, Marin, et autres
Publié: (2025)
par: Bougeret, Marin, et autres
Publié: (2025)
Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
par: Kaul, Matthias, et autres
Publié: (2025)
par: Kaul, Matthias, et autres
Publié: (2025)
Expander Decomposition for Non-Uniform Vertex Measures
par: Agassy, Daniel, et autres
Publié: (2025)
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)
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)
par: Bhore, Sujoy, et autres
Publié: (2024)
Capacitated Partition Vertex Cover and Partition Edge Cover
par: Dabas, Rajni, et autres
Publié: (2025)
par: Dabas, Rajni, et autres
Publié: (2025)
An Optimal Algorithm for Stochastic Vertex Cover
par: Brand, Jan van den, et autres
Publié: (2026)
par: Brand, Jan van den, et autres
Publié: (2026)
Weighted Partition Vertex and Edge Cover
par: Dabas, Rajni, et autres
Publié: (2025)
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)
par: Akhtar, Sheikh Shakil, et autres
Publié: (2025)
Width Parameters for Minimum Flow Decomposition
par: Grigorjew, Andreas, et autres
Publié: (2024)
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)
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)
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)
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)
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)
par: Solomon, Shay, et autres
Publié: (2023)
A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
par: Kwok, Shawxing
Publié: (2025)
par: Kwok, Shawxing
Publié: (2025)
Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
par: Chuzhoy, Julia, et autres
Publié: (2025)
par: Chuzhoy, Julia, et autres
Publié: (2025)
Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
par: Li, Xizhe, et autres
Publié: (2026)
par: Li, Xizhe, et autres
Publié: (2026)
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
par: Bentert, Matthias, et autres
Publié: (2025)
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)
par: Hua, Kevin, et autres
Publié: (2024)
The Complexity of Temporal Vertex Cover in Small-Degree Graphs
par: Hamm, Thekla, et autres
Publié: (2022)
par: Hamm, Thekla, et autres
Publié: (2022)
Cluster Vertex Deletion on Chordal Graphs
par: Cao, Yixin, et autres
Publié: (2026)
par: Cao, Yixin, et autres
Publié: (2026)
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
par: Bentert, Matthias, et autres
Publié: (2024)
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)
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)
par: Jiang, Yonggang, et autres
Publié: (2025)
FPT Approximations for Connected Maximum Coverage
par: Inamdar, Tanmay, et autres
Publié: (2026)
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)
par: Dong, Sally, et autres
Publié: (2023)
9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
par: Çivril, Ali
Publié: (2024)
par: Çivril, Ali
Publié: (2024)
The Power of Greedy for Online Minimum Cost Matching on the Line
par: Balkanski, Eric, et autres
Publié: (2022)
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)
par: Fischer, Manuela, et autres
Publié: (2021)
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)