Imagen de Portada

Quasilinear-time eccentricities computation, and more, on median graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bergé, Pierre, Ducoffe, Guillaume, Habib, Michel
Formato:	Preprint
Publicado:	2024
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 fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
por: Ducoffe, Guillaume
Publicado: (2026)

Bow Metrics and Hyperbolicity
por: Dragan, Feodor F., et al.
Publicado: (2024)

Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
por: Aubian, Guillaume, et al.
Publicado: (2025)

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

Practical Computation of Graph VC-Dimension
por: Coudert, David, et al.
Publicado: (2024)

Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
por: Dragan, Feodor F., et al.
Publicado: (2018)

$α_i$-Metric Graphs: Hyperbolicity
por: Dragan, Feodor F., et al.
Publicado: (2024)

The Canadian Traveller Problem on outerplanar graphs
por: Beaudou, Laurent, et al.
Publicado: (2024)

Distributed computation of temporal twins in periodic undirected time-varying graphs
por: Azerouk, Lina, et al.
Publicado: (2024)

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
por: Driemel, Anne, et al.
Publicado: (2025)

Fast approximation algorithms for the 1-median problem on real-world large graphs
por: Ueta, Keisuke, et al.
Publicado: (2025)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
por: Charbit, Pierre, et al.
Publicado: (2025)

Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
por: Wesołowski, Adam, et al.
Publicado: (2025)

A more efficient algorithm to compute the Rand Index for change-point problems
por: Prates, Lucas de Oliveira
Publicado: (2021)

Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor
por: Csikós, Mónika, et al.
Publicado: (2023)

On the power of standard DFS and BFS
por: Bui-Xuan, Binh-Minh, et al.
Publicado: (2026)

The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs
por: Jaberi, Raed, et al.
Publicado: (2024)

Faster diameter computation in graphs of bounded Euler genus
por: Kluk, Kacper, et al.
Publicado: (2025)

Lower bounds for graph reconstruction with maximal independent set queries
por: Michel, Lukas, et al.
Publicado: (2024)

Improved exploration of temporal graphs
por: Bastide, Paul, et al.
Publicado: (2025)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
por: Kowalik, Lukasz
Publicado: (2024)

Learning-Augmented Algorithms for $k$-median via Online Learning
por: Hebbar, Anish, et al.
Publicado: (2026)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
por: Makarychev, Konstantin, et al.
Publicado: (2025)

Approximation algorithms for Job Scheduling with reconfigurable resources
por: Bergé, Pierre, et al.
Publicado: (2023)

A more accurate rational non-commutative algorithm for multiplying 4x4 matrices using 48 multiplications
por: Dumas, Jean-Guillaume, et al.
Publicado: (2026)

Locally computing edge orientations
por: Mitrović, Slobodan, et al.
Publicado: (2025)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
por: Karczmarz, Adam, et al.
Publicado: (2024)

A more versatile model for enumerative kernelization: a case study for Vertex Cover
por: Bougeret, Marin, et al.
Publicado: (2026)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
por: Bathie, Gabriel, et al.
Publicado: (2025)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
por: Lachish, Oded, et al.
Publicado: (2026)

Meeting times on graphs in near-cubic time
por: McAvoy, Alex
Publicado: (2026)

Differentially private graph coloring
por: Xie, Michael, et al.
Publicado: (2026)

Private graph colouring with limited defectiveness
por: Christiansen, Aleksander B. G., et al.
Publicado: (2024)

Practical algorithms for Hierarchical overlap graphs
por: Talera, Saumya, et al.
Publicado: (2024)

The trace reconstruction problem for spider graphs
por: Sun, Alec, et al.
Publicado: (2022)

Sparse Random Matrices for Dimensionality Reduction
por: Mackenzie, Pierre
Publicado: (2025)

Efficient algorithms for computing bisimulations for nondeterministic fuzzy transition systems
por: Nguyen, Linh Anh
Publicado: (2024)

A computational study of Gomory-Hu construction tree algorithms
por: Kolmogorov, Vladimir
Publicado: (2022)

Spanning tree congestion of proper interval graphs
por: Otachi, Yota
Publicado: (2026)

Approximating optimization problems in graphs with locational uncertainty
por: Bougeret, Marin, et al.
Publicado: (2022)