Buchumschlag

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chakraborty, Dibyayan, Vaxès, Yann
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Isometric path complexity of graphs
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2022)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
von: Ducoffe, Guillaume
Veröffentlicht: (2026)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Sequence graphs realizations and ambiguity in language models
von: Khalife, Sammy, et al.
Veröffentlicht: (2024)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Enumerating models of DNF faster: breaking the dependency on the formula size
von: Capelli, Florent, et al.
Veröffentlicht: (2018)

From Amortized to Worst Case Delay in Enumeration Algorithms
von: Capelli, Florent, et al.
Veröffentlicht: (2021)

On approximability of the Permanent of PSD matrices
von: Ebrahimnejad, Farzam, et al.
Veröffentlicht: (2024)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
von: Fujie, Yuto, et al.
Veröffentlicht: (2025)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

On the complexity and approximability of Bounded access Lempel Ziv coding
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2024)

MAX BISECTION might be harder to approximate than MAX CUT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

A note on approximating the average degree of bounded arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2026)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
von: Björklund, Andreas, et al.
Veröffentlicht: (2025)

On $G^p$-unimodality of radius functions in graphs: structure and algorithms
von: Chalopin, Jérémie, et al.
Veröffentlicht: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
von: Dell, Holger, et al.
Veröffentlicht: (2022)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
von: Yang, Yang
Veröffentlicht: (2025)

Gray Codes With Constant Delay and Constant Auxiliary Space
von: Amarilli, Antoine, et al.
Veröffentlicht: (2026)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
von: Frei, Fabian, et al.
Veröffentlicht: (2024)

The complexity of testing all properties of planar graphs, and the role of isomorphism
von: Basu, Sabyasachi, et al.
Veröffentlicht: (2021)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
von: Apers, Simon, et al.
Veröffentlicht: (2021)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
von: Dumas, Maël, et al.
Veröffentlicht: (2022)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
von: Kluk, Kacper, et al.
Veröffentlicht: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Smoothed analysis for graph isomorphism
von: Anastos, Michael, et al.
Veröffentlicht: (2024)

Complexity of Finding and Enumerating Interconnection Trees
von: Demange, Noé, et al.
Veröffentlicht: (2026)

On the complexity of global Roman domination problem in graphs
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2026)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
von: Huang, Neng, et al.
Veröffentlicht: (2024)

Clifford testing: algorithms and lower bounds
von: Hinsche, Marcel, et al.
Veröffentlicht: (2025)

Fast quantum algorithm for differential equations
von: Bagherimehrab, Mohsen, et al.
Veröffentlicht: (2023)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
von: Bengali, Vedangi, et al.
Veröffentlicht: (2024)

An unconditional lower bound for the active-set method on the hypercube
von: Disser, Yann, et al.
Veröffentlicht: (2025)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Maximum $k$- vs. $\ell$-colourings of graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2023)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
von: Sarkar, Rohit Sarma, et al.
Veröffentlicht: (2024)

Channel allocation revisited through 1-extendability of graphs
von: Busson, Anthony, et al.
Veröffentlicht: (2024)