Image de couverture de livre

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs

Fuente: arXiv

Enregistré dans:

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

Documents similaires

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
par: Chakraborty, Dibyayan, et autres
Publié: (2024)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
par: Kim, Eun Jung, et autres
Publié: (2022)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
par: Dumas, Maël, et autres
Publié: (2022)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
par: Kluk, Kacper, et autres
Publié: (2025)

On the complexity of global Roman domination problem in graphs
par: Reddy, Sangam Balchandar, et autres
Publié: (2026)

Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
par: Dragan, Feodor F., et autres
Publié: (2018)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
par: Nederlof, Jesper
Publié: (2026)

An alignment problem
par: McDaniel, Emma L., et autres
Publié: (2024)

Analyzing and Leveraging the $k$-Sensitivity of LZ77
par: Bathie, Gabriel, et autres
Publié: (2026)

The complexity of testing all properties of planar graphs, and the role of isomorphism
par: Basu, Sabyasachi, et autres
Publié: (2021)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
par: Yang, Yang
Publié: (2024)

A lossless a priori splitting rule for split-delivery routing problems
par: Jones, Bo, et autres
Publié: (2025)

Constructing self-referential instances for the clique problem
par: Li, Jiaqi, et autres
Publié: (2026)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
par: Austrin, Per, et autres
Publié: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
par: Esmer, Barış Can, et autres
Publié: (2022)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
par: Yang, Yang
Publié: (2025)

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
par: Bendotti, Pascale, et autres
Publié: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
par: Scheder, Dominik, et autres
Publié: (2025)

Smoothed analysis for graph isomorphism
par: Anastos, Michael, et autres
Publié: (2024)

Quasilinear-time eccentricities computation, and more, on median graphs
par: Bergé, Pierre, et autres
Publié: (2024)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
par: Huang, Neng, et autres
Publié: (2024)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
par: Le, Hoang-Oanh, et autres
Publié: (2024)

Sequence graphs realizations and ambiguity in language models
par: Khalife, Sammy, et autres
Publié: (2024)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
par: Li, Tiange, et autres
Publié: (2026)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
par: Prunet, Thibault, et autres
Publié: (2023)

A Note on Approximability of Densest At-Least-k-Subgraph
par: Laekhanukit, Bundit, et autres
Publié: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2025)

A Simple Proof that Ricochet Robots is PSPACE-Complete
par: Balanza-Martinez, Jose, et autres
Publié: (2024)

A Space-space Trade-off for Directed st-Connectivity
par: Edenhofer, Roman
Publié: (2026)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
par: Clinch, Katie, et autres
Publié: (2025)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
par: Lehner, Lisa, et autres
Publié: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
par: Kunisky, Dmitriy, et autres
Publié: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
par: Garg, Sumegha, et autres
Publié: (2026)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
par: Bai, Tian, et autres
Publié: (2026)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
par: Gholizadeh, Hossein, et autres
Publié: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
par: Buhrman, Harry, et autres
Publié: (2025)

A tight quasi-polynomial bound for Global Label Min-Cut
par: Jaffke, Lars, et autres
Publié: (2022)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
par: Kenig, Batya
Publié: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
par: Braverman, Mark, et autres
Publié: (2024)