Source author record

Muad Abu-Ata

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 math.MG Social and Information Networks

Catalog footprint

Research overview

2works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

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.