Source author record

Feodor F. Dragan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO math.MG Social and Information Networks

Catalog footprint

Research overview

10works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

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 metric spaces. It is also known that every graph isometrically embeds into a Helly graph, making the latter an important class of graphs in Metric Graph Theory. We study diameter, radius and all eccentricity computations within the Helly graphs. Under plausible complexity assumptions, neither the diameter nor the radius can be computed in truly subquadratic time on general graphs. In contrast to these negative results, it was recently shown that the radius and the diameter of an $n$ -vertex $m$ -edge Helly graph $G$ can be computed with high probability in $\tilde{\mathcal O}(m\sqrt{n})$ time (i.e., subquadratic in $n+m$ ). In this paper, we improve that result by presenting a deterministic ${\mathcal O}(m\sqrt{n})$ time algorithm which computes not only the radius and the diameter but also all vertex eccentricities in a Helly graph. Furthermore, we give a parameterized linear-time algorithm for this problem on Helly graphs, with the parameter being the Gromov hyperbolicity $δ$ . More specifically, we show that the radius and a central vertex of an $m$ -edge $δ$ -hyperbolic Helly graph $G$ can be computed in $\mathcal O(δm)$ time and that all vertex eccentricities in $G$ can be computed in $\mathcal O(δ^2 m)$ time. To show this more general result, we heavily use our new structural properties obtained for Helly graphs.

preprint2020arXiv

Eccentricity function in distance-hereditary graphs

A graph $G=(V,E)$ is distance hereditary if every induced path of $G$ is a shortest path. In this paper, we show that the eccentricity function $e(v)=\max\{d(v,u): u\in V\}$ in any distance-hereditary graph $G$ is almost unimodal, that is, every vertex $v$ with $e(v)> rad(G)+1$ has a neighbor with smaller eccentricity. Here, $rad(G)=\min\{e(v): v\in V\}$ is the radius of graph $G$ . Moreover, we use this result to fully characterize the centers of distance-hereditary graphs. Several bounds on the eccentricity of a vertex with respect to its distance to the center of $G$ or to the ends of a diametral path are established. Finally, we propose a new linear time algorithm to compute all eccentricities in a distance-hereditary graph.

preprint2020arXiv

Eccentricity terrain of $δ$ -hyperbolic graphs

A graph $G=(V,E)$ is $δ$ -hyperbolic if for any four vertices $u,v,w,x$ , the two larger of the three distance sums $d(u,v)+d(w,x)$ , $d(u,w)+d(v,x)$ , and $d(u,x)+d(v,w)$ differ by at most $2δ\geq 0$ . Recent work shows that many real-world graphs have small hyperbolicity $δ$ . This paper describes the eccentricity terrain of a $δ$ -hyperbolic graph. The eccentricity function $e_G(v)=\max\{d(v,u) : u \in V\}$ partitions the vertex set of $G$ into eccentricity layers $C_{k}(G) = \{v \in V : e(v)=rad(G)+k\}$ , $k \in \mathbb{N}$ , where $rad(G)=\min\{e_G(v): v\in V\}$ is the radius of $G$ . The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of $β$ -pseudoconvexity, which implies Gromov's $ε$ -quasiconvexity, and illustrates the abundance of pseudoconvex sets in $δ$ -hyperbolic graphs. In particular, it shows that all sets $C_{\leq k}(G)=\{v\in V : e_G(v) \leq rad(G) + k\}$ , $k\in \mathbb{N}$ , are $(2δ-1)$ -pseudoconvex. Additionally, several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. An $O(δ|E|)$ time eccentricity approximation $\hat{e}(v)$ , for all $v\in V$ , is presented that uses distances to two mutually distant vertices and satisfies $e_G(v)-2δ\leq \hat{e}(v) \leq {e_G}(v)$ . It also shows existence of two eccentricity approximating spanning trees $T$ , one constructible in $O(δ|E|)$ time and the other in $O(|E|)$ time, which satisfy ${e}_G(v) \leq e_T(v) \leq {e}_G(v)+4δ+1$ and ${e}_G(v) \leq e_T(v) \leq {e}_G(v)+6δ$ , respectively. Thus, the eccentricity terrain of a tree gives a good approximation (up-to an additive error $O(δ))$ of the eccentricity terrain of a $δ$ -hyperbolic graph.

preprint2020arXiv

Helly-gap of a graph and vertex eccentricities

A new metric parameter for a graph, Helly-gap, is introduced. A graph $G$ is called $α$ -weakly-Helly if any system of pairwise intersecting disks in $G$ has a nonempty common intersection when the radius of each disk is increased by an additive value $α$ . The minimum $α$ for which a graph $G$ is $α$ -weakly-Helly is called the Helly-gap of $G$ and denoted by $α(G)$ . The Helly-gap of a graph $G$ is characterized by distances in the injective hull $\mathcal{H}(G)$ , which is a (unique) minimal Helly graph which contains $G$ as an isometric subgraph. This characterization is used as a tool to generalize many eccentricity related results known for Helly graphs ( $α(G)=0$ ), as well as for chordal graphs ( $α(G)\le 1$ ), distance-hereditary graphs ( $α(G)\le 1$ ) and $δ$ -hyperbolic graphs ( $α(G)\le 2δ$ ), to all graphs, parameterized by their Helly-gap $α(G)$ . Several additional graph classes are shown to have a bounded Helly-gap, including AT-free graphs and graphs with bounded tree-length, bounded chordality or bounded $α_i$ -metric.

preprint2020arXiv

Injective hulls of various graph classes

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, there exists a unique smallest Helly graph H(G) into which G isometrically embeds; H(G) is called the injective hull of G. Motivated by this, we investigate the structural properties of the injective hulls of various graph classes. We say that a class of graphs $\mathcal{C}$ is closed under Hellification if $G \in \mathcal{C}$ implies $H(G) \in \mathcal{C}$ . We identify several graph classes that are closed under Hellification. We show that permutation graphs are not closed under Hellification, but chordal graphs, square-chordal graphs, and distance-hereditary graphs are. Graphs that have an efficiently computable injective hull are of particular interest. A linear-time algorithm to construct the injective hull of any distance-hereditary graph is provided and we show that the injective hull of several graphs from some other well-known classes of graphs are impossible to compute in subexponential time. In particular, there are split graphs, cocomparability graphs, bipartite graphs G such that H(G) contains $Ω(a^{n})$ vertices, where $n=|V(G)|$ and $a>1$ .

preprint2016arXiv

Core congestion is inherent in hyperbolic networks

We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network $G$ admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset $X$ of vertices of a $δ$ -hyperbolic graph $G$ there exists a vertex $m$ of $G$ such that the disk $D(m,4 δ)$ of radius $4 δ$ centered at $m$ intercepts at least one half of the total flow between all pairs of vertices of $X$ , where the flow between two vertices $x,y\in X$ is carried by geodesic (or quasi-geodesic) $(x,y)$ -paths. A set $S$ intercepts the flow between two nodes $x$ and $y$ if $S$ intersect every shortest path between $x$ and $y$ . Differently from what was conjectured by Jonckheere et al., we show that $m$ is not (and cannot be) the center of mass of $X$ but is a node close to the median of $X$ in the so-called injective hull of $X$ . In case of non-uniform traffic between nodes of $X$ (in this case, the unit flow exists only between certain pairs of nodes of $X$ defined by a commodity graph $R$ ), we prove a primal-dual result showing that for any $ρ>5δ$ the size of a $ρ$ -multi-core (i.e., the number of disks of radius $ρ$ ) intercepting all pairs of $R$ is upper bounded by the maximum number of pairwise $(ρ-3δ)$ -apart pairs of $R$ .

preprint2015arXiv

Minimum Eccentricity Shortest Paths in some Structured Graph Classes

We investigate the Minimum Eccentricity Shortest Path problem in some structured graph classes. It asks for a given graph to find a shortest path with minimum eccentricity. Although it is NP-hard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distance-hereditary graphs (generalizing the previous result for trees) and give a generalised approach which allows to solve the problem in polynomial time for other graph classes. This includes chordal graphs, dually chordal graphs, graphs with bounded tree-length, and graphs with bounded hyperbolicity. Additionally, we give a simple algorithm to compute an additive approximation for graphs with bounded tree-length and graphs with bounded hyperbolicity.

preprint2014arXiv

Line-distortion, Bandwidth and Path-length of a graph

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-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show: - if a graph $G$ can be embedded into the line with distortion $k$ , then $G$ admits a Robertson-Seymour's path-decomposition with bags of diameter at most $k$ in $G$ ; - for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem; - there is an efficient 2-approximation algorithm for computing the path-length of an arbitrary graph; - AT-free graphs and some intersection families of graphs have path-length at most 2; - for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem.

preprint2014arXiv

Metric tree-like structures in real-life networks: an empirical study

Based on solid theoretical foundations, we present strong evidences that a number of real-life networks, taken from different domains like Internet measurements, biological data, web graphs, social and collaboration networks, exhibit tree-like structures from a metric point of view. We investigate few graph parameters, namely, the tree-distortion and the tree-stretch, the tree-length and the tree-breadth, the Gromov's hyperbolicity, the cluster-diameter and the cluster-radius in a layering partition of a graph, which capture and quantify this phenomenon of being metrically close to a tree. By bringing all those parameters together, we not only provide efficient means for detecting such metric tree-like structures in large-scale networks but also show how such structures can be used, for example, to efficiently and compactly encode approximate distance and almost shortest path information and to fast and accurately estimate diameters and radii of those networks. Estimating the diameter and the radius of a graph or distances between its arbitrary vertices are fundamental primitives in many data and graph mining algorithms.

preprint2012arXiv

Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences

In this paper, we study collective additive tree spanners for families of graphs enjoying special Robertson-Seymour's tree-decompositions, and demonstrate interesting consequences of obtained results. We say that a graph $G$ {\em admits a system of $μ$ collective additive tree $r$ -spanners} (resp., {\em multiplicative tree $t$ -spanners}) if there is a system $\cT(G)$ of at most $μ$ spanning trees of $G$ such that for any two vertices $x,y$ of $G$ a spanning tree $T\in \cT(G)$ exists such that $d_T(x,y)\leq d_G(x,y)+r$ (resp., $d_T(x,y)\leq t\cdot d_G(x,y)$ ). When $μ=1$ one gets the notion of {\em additive tree $r$ -spanner} (resp., {\em multiplicative tree $t$ -spanner}). It is known that if a graph $G$ has a multiplicative tree $t$ -spanner, then $G$ admits a Robertson-Seymour's tree-decomposition with bags of radius at most $\lceil{t/2}\rceil$ in $G$ . We use this to demonstrate that there is a polynomial time algorithm that, given an $n$ -vertex graph $G$ admitting a multiplicative tree $t$ -spanner, constructs a system of at most $\log_2 n$ collective additive tree $O(t\log n)$ -spanners of $G$ . That is, with a slight increase in the number of trees and in the stretch, one can "turn" a multiplicative tree spanner into a small set of collective additive tree spanners. We extend this result by showing that if a graph $G$ admits a multiplicative $t$ -spanner with tree-width $k-1$ , then $G$ admits a Robertson-Seymour's tree-decomposition each bag of which can be covered with at most $k$ disks of $G$ of radius at most $\lceil{t/2}\rceil$ each. This is used to demonstrate that, for every fixed $k$ , there is a polynomial time algorithm that, given an $n$ -vertex graph $G$ admitting a multiplicative $t$ -spanner with tree-width $k-1$ , constructs a system of at most $k(1+ \log_2 n)$ collective additive tree $O(t\log n)$ -spanners of $G$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Feodor F. Dragan

Research overview

Is this your work?

10 publications

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

Eccentricity function in distance-hereditary graphs

Eccentricity terrain of $δ$ -hyperbolic graphs

Helly-gap of a graph and vertex eccentricities

Injective hulls of various graph classes

Core congestion is inherent in hyperbolic networks

Minimum Eccentricity Shortest Paths in some Structured Graph Classes

Line-distortion, Bandwidth and Path-length of a graph

Metric tree-like structures in real-life networks: an empirical study

Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences

See the researcher in context

Building this map preview

Feodor F. Dragan

Research overview

Is this your work?

10 publications

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

Eccentricity function in distance-hereditary graphs

Eccentricity terrain of δδδ-hyperbolic graphs

Helly-gap of a graph and vertex eccentricities

Injective hulls of various graph classes

Core congestion is inherent in hyperbolic networks

Minimum Eccentricity Shortest Paths in some Structured Graph Classes

Line-distortion, Bandwidth and Path-length of a graph

Metric tree-like structures in real-life networks: an empirical study

Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences

See the researcher in context

Building this map preview

Eccentricity terrain of $δ$ -hyperbolic graphs