Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Davies-Peck, Peter
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
por: Kolmogorov, Vladimir, et al.
Publicado: (2026)

Parameterized Algorithms for Minimum Sum Vertex Cover
por: Aute, Shubhada, et al.
Publicado: (2024)

Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model
por: Robinson, Peter, et al.
Publicado: (2025)

New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs
por: Heck, Sophia, et al.
Publicado: (2026)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
por: D'Angelo, Gianlorenzo, et al.
Publicado: (2025)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
por: Kobayashi, Yusuke, et al.
Publicado: (2026)

Approximately: Independence Implies Vertex Cover
por: Har-Peled, Sariel
Publicado: (2023)

Approximating Maximum Matching Requires Almost Quadratic Time
por: Behnezhad, Soheil, et al.
Publicado: (2024)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
por: Ahi, Mridul, et al.
Publicado: (2025)

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

Enumeration kernels for Vertex Cover and Feedback Vertex Set
por: Bougeret, Marin, et al.
Publicado: (2025)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
por: Kaul, Matthias, et al.
Publicado: (2025)

Expander Decomposition for Non-Uniform Vertex Measures
por: Agassy, Daniel, et al.
Publicado: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
por: DeHaan, Ian, et al.
Publicado: (2024)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
por: Bhore, Sujoy, et al.
Publicado: (2024)

Capacitated Partition Vertex Cover and Partition Edge Cover
por: Dabas, Rajni, et al.
Publicado: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
por: Brand, Jan van den, et al.
Publicado: (2026)

Weighted Partition Vertex and Edge Cover
por: Dabas, Rajni, et al.
Publicado: (2025)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
por: Akhtar, Sheikh Shakil, et al.
Publicado: (2025)

Width Parameters for Minimum Flow Decomposition
por: Grigorjew, Andreas, et al.
Publicado: (2024)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
por: Mahabadi, Sepideh, et al.
Publicado: (2025)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
por: Gupta, Sushmita, et al.
Publicado: (2024)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
por: Saito, Rin, et al.
Publicado: (2025)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
por: Chuzhoy, Julia, et al.
Publicado: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
por: Solomon, Shay, et al.
Publicado: (2023)

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

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
por: Chuzhoy, Julia, et al.
Publicado: (2025)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
por: Li, Xizhe, et al.
Publicado: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
por: Bentert, Matthias, et al.
Publicado: (2025)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
por: Hua, Kevin, et al.
Publicado: (2024)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
por: Hamm, Thekla, et al.
Publicado: (2022)

Cluster Vertex Deletion on Chordal Graphs
por: Cao, Yixin, et al.
Publicado: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
por: Bentert, Matthias, et al.
Publicado: (2024)

A Fully-dynamic Approximation Algorithm for Maximum Weight b-Matchings in Graphs
por: Brandt-Tumescheit, Fabian, et al.
Publicado: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
por: Jiang, Yonggang, et al.
Publicado: (2025)

FPT Approximations for Connected Maximum Coverage
por: Inamdar, Tanmay, et al.
Publicado: (2026)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
por: Dong, Sally, et al.
Publicado: (2023)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
por: Çivril, Ali
Publicado: (2024)

The Power of Greedy for Online Minimum Cost Matching on the Line
por: Balkanski, Eric, et al.
Publicado: (2022)

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