Search

Abstract Let P be a path graph of n vertices embedded in a metric space. We consider the problem of adding a new edge to P such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in O (n log 3 ⁡ n) time. In this paper, based on new observations and different algorithmic techniques, we present an O (n log ⁡ n) time algorithm. [ABSTRACT FROM AUTHOR]

A star is a graph in which some node is incident with every edge of the graph, i.e., a graph of diameter at most 2. A star forest is a graph in which each connected component is a star. Given a connected graph G in which the edges may be weighted positively. A spanning star forest of G is a subgraph of G which is a star forest spanning the nodes of G. The size of a spanning star forest F of G is defined to be the number of edges of F if G is unweighted and the total weight of all edges of F if G is weighted. We are interested in the problem of finding a Maximum Weight spanning Star Forest (MWSFP) in G. In [C. T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller and L. Zhang, Approximating the spanning star forest problem and its applications to genomic sequence alignment, SIAM J. Comput. 38(3) (2008) 946-962], the authors introduced the MWSFP and proved its NP-hardness. They also gave a polynomial time algorithm for the MWSF problem when G is a tree. In this paper, we present a linear time algorithm that solves the MSWF problem when G is a cactus. [ABSTRACT FROM AUTHOR]

The eccentricity of a node in a graph is defined as the length of a longest shortest path starting at that node. The eccentricity distribution over all nodes is a relevant descriptive property of the graph, and its extreme values allow the derivation of measures such as the radius, diameter, center and periphery of the graph. This paper describes two new methods for computing the eccentricity distribution of large graphs such as social networks, web graphs, biological networks and routing networks.We first propose an exact algorithm based on eccentricity lower and upper bounds, which achieves significant speedups compared to the straightforward algorithm when computing both the extreme values of the distribution as well as the eccentricity distribution as a whole. The second algorithm that we describe is a hybrid strategy that combines the exact approach with an efficient sampling technique in order to obtain an even larger speedup on the computation of the entire eccentricity distribution. We perform an extensive set of experiments on a number of large graphs in order to measure and compare the performance of our algorithms, and demonstrate how we can efficiently compute the eccentricity distribution of various large real-world graphs. [ABSTRACT FROM AUTHOR]

Metacyclic graphs, which include supertoroids as a subclass, have been shown to possess interesting properties and potential applications in implementing moderate- to large-size parallel processors with fairly small node degrees. Wu, Lakshmivarahan, and Dhall (J. Parallel Distrib. Comput. 60 (2000), pp. 539-565) have described a deterministic, distributed routing scheme for certain subclasses of metacyclic graphs. However, they offer no proof that the scheme is a shortest-path routing algorithm and do not indicate whether or how their scheme may be extended to the entire class of metacyclic graphs. In this paper, we provide a near-shortest-path, deterministic routing algorithm that is applicable to any metacyclic graph and derive a bound for the diameter of such graphs. [ABSTRACT FROM AUTHOR]

Let γ pr ( G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ pr ( G – v) < γ pr ( G). We call these graphs γ pr -critical. In this paper, we present a method of constructing γ pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ pr -critical graph is at most $$\frac{3}{2}(\gamma_{pr} (G)-2)$$ and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. [ABSTRACT FROM AUTHOR]