Buchumschlag

Girth Approximations in the CONGEST Model

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chechik, Shiri, Lifshitz, Gur, Mukhtar, Doron
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Streaming Edge Coloring with Subquadratic Palette Size
von: Chechik, Shiri, et al.
Veröffentlicht: (2023)

Faster Algorithms for Dual-Failure Replacement Paths
von: Chechik, Shiri, et al.
Veröffentlicht: (2024)

Faster Deterministic Streaming Vertex Coloring
von: Chechik, Shiri, et al.
Veröffentlicht: (2026)

Improved Streaming Edge Coloring
von: Chechik, Shiri, et al.
Veröffentlicht: (2025)

Approximate Distance Sensitivity Oracles in Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2023)

Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model
von: Jauregui, Benjamin, et al.
Veröffentlicht: (2018)

Deterministic Edge Coloring with few Colors in CONGEST
von: Blikstad, Joakim, et al.
Veröffentlicht: (2026)

Simpler and Improved Replacement Path Coverings
von: Bilò, Davide, et al.
Veröffentlicht: (2026)

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
von: Manoharan, Vignesh, et al.
Veröffentlicht: (2023)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Online Coloring for Graphs of Large Odd Girth
von: Yoneda, Hirotaka, et al.
Veröffentlicht: (2026)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Approximations and Hardness of Packing Partially Ordered Items
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs
von: Li, Tongyang, et al.
Veröffentlicht: (2024)

Deterministic Even-Cycle Detection in Broadcast CONGEST
von: Fraigniaud, Pierre, et al.
Veröffentlicht: (2024)

Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
von: Manoharan, Vignesh, et al.
Veröffentlicht: (2022)

Non-Linear Paging
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
von: Faour, Salwa, et al.
Veröffentlicht: (2025)

Unsplittable Flow on a Short Path
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2023)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2023)

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
von: Gall, François Le, et al.
Veröffentlicht: (2018)

Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
von: Konstantinovsky, Thomas, et al.
Veröffentlicht: (2026)

Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions
von: Chang, Yi-Jun, et al.
Veröffentlicht: (2022)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
von: Baumecker, Malte, et al.
Veröffentlicht: (2025)

Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
von: Suzuki, Ryo, et al.
Veröffentlicht: (2026)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
von: Lenzen, Christoph, et al.
Veröffentlicht: (2024)

On Approximating Cutwidth and Pathwidth
von: Bansal, Nikhil, et al.
Veröffentlicht: (2023)

Approximating $δ$-Covering
von: Hartmann, Tim A., et al.
Veröffentlicht: (2024)

An algorithmic Polynomial Freiman-Ruzsa theorem
von: Castro-Silva, Davi, et al.
Veröffentlicht: (2026)

The Impact of Approximation on Algorithmic Progress
von: Li, Jeffery, et al.
Veröffentlicht: (2026)

Hardness and Approximation for Coloring Digraphs
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2026)

Consistent Low-Rank Approximation
von: Woodruff, David P., et al.
Veröffentlicht: (2026)

Optimized 2-Approximation of Treewidth
von: Belbasi, Mahdi, et al.
Veröffentlicht: (2024)

Approximate counting of permutation patterns
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2024)

Supermodular Approximation of Norms and Applications
von: Kesselheim, Thomas, et al.
Veröffentlicht: (2024)

Approximating Small Sparse Cuts
von: Anand, Aditya, et al.
Veröffentlicht: (2024)