14 citations · 55 across the 23 of their papers we have counts for
27 papers
Gradient-Aligned Pair Selection for Personalized Preference Optimization
Ruoming Jin, Xinyu Li, Hao Zhou +6
Personalizing large language models (LLMs) requires aligning generation behavior with user-specific preferences rather than aggregate quality. While Direct Preference Optimization…
Lower bounds on collective additive spanners
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler +1
In this paper we present various lower bound results on collective tree spanners and on spanners of bounded treewidth. A graph is said to admit a system of collective addit…
Graph parameters that are coarsely equivalent to path-length
Feodor F. Dragan, Ekkehard Köhler
Two graph parameters are said to be coarsely equivalent if they are within constant factors from each other for every graph . Recently, several graph parameters were shown to be…
On -unimodality of radius functions in graphs: structure and algorithms
Jérémie Chalopin, Victor Chepoi, Feodor Dragan +2
For every weight assignment to the vertices in a graph , the radius function maps every vertex of to its largest weighted distance to the other vertices. The cente…
Graph parameters that are coarsely equivalent to tree-length
Feodor F. Dragan
Two graph parameters are said to be coarsely equivalent if they are within constant factors from each other for every graph . Recently, several graph parameters were shown to be…
Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
Guillaume Aubian, Filippo Brunelli, Feodor F Dragan +4
Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal as…
Bow Metrics and Hyperbolicity
Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1
A ()-bow metric was defined in (Dragan & Ducoffe, 2023) as a far reaching generalization of an -metric (which is equivalent to a ()-bow metric). A graph is…
-Metric Graphs: Hyperbolicity
Feodor F. Dragan, Guillaume Ducoffe
A graph is called -metric () if it satisfies the following -metric property for every vertices and : if a shortest path between and a…
-Metric Graphs: Radius, Diameter and all Eccentricities
Feodor F. Dragan, Guillaume Ducoffe
We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph…
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
Feodor F. Dragan, Guillaume Ducoffe, Heather M. Guarnera
A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. The class of Helly graphs is the discrete analogue of the class of hyperconvex m…
Injective hulls of various graph classes
Heather M. Guarnera, Feodor F. Dragan, Arne Leitert
A graph is Helly if its disks satisfy the Helly property, i.e., every family of pairwise intersecting disks in G has a common intersection. It is known that for every graph G, ther…
Helly-gap of a graph and vertex eccentricities
Feodor F. Dragan, Heather M. Guarnera
A new metric parameter for a graph, Helly-gap, is introduced. A graph is called -weakly-Helly if any system of pairwise intersecting disks in has a nonempty common inter…
Eccentricity terrain of -hyperbolic graphs
Feodor F. Dragan, Heather M. Guarnera
A graph is -hyperbolic if for any four vertices , the two larger of the three distance sums , , and differ by at…
A story of diameter, radius and Helly property
Feodor F. Dragan, Guillaume Ducoffe
A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. Motivated by previous work on dually chordal graphs and graphs of bounded distan…
Eccentricity function in distance-hereditary graphs
Feodor F. Dragan, Heather M. Guarnera
A graph is distance hereditary if every induced path of is a shortest path. In this paper, we show that the eccentricity function in any…
Pruned Landmark Labeling Meets Vertex Centric Computation: A Surprisingly Happy Marriage!
Ruoming Jin, Zhen Peng, Wendell Wu +3
In this paper, we study how the Pruned Landmark Labeling (PPL) algorithm can be parallelized in a scalable fashion, producing the same results as the sequential algorithm. More spe…
Fast approximation of centrality and distances in hyperbolic graphs
Victor Chepoi, Feodor F. Dragan, Michel Habib +2
We show that the eccentricities (and thus the centrality indices) of all vertices of a -hyperbolic graph can be computed in linear time with an additive one-sided erro…
Fast approximation and exact computation of negative curvature parameters of graphs
Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan +3
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov…
Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1
In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomial-time algorithms. We specifically target radius (minimum eccentricity)…
Obstructions to a small hyperbolicity in Helly graphs
Feodor F. Dragan, Heather M. Guarnera
It is known that for every graph there exists the smallest Helly graph into which isometrically embeds ( is called the injective hull of ) such th…
Parameterized Approximation Algorithms for some Location Problems in Graphs
Arne Leitert, Feodor F. Dragan
We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) -Domination problem and the (Connected) -Center problem for unweighted a…
Slimness of graphs
Feodor F. Dragan, Abdulhakeem Mohammed
Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph , a geodesic triangle with is the unio…
Core congestion is inherent in hyperbolic networks
Victor Chepoi, Feodor F. Dragan, Yann Vaxès
We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network admits a core, thus answer…
Line-distortion, Bandwidth and Path-length of a graph
Feodor F. Dragan, Ekkehard Köhler, Arne Leitert
We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson-Seymour's path-decompo…