Search

The following problem is solved: determine a point on a tree having the property that the sum of the products of the intensities of its vertices by the corresponding distances to that point is a minimum. The proposed algorithm is reduced to the stepwise application to the tree of truncation of its vertices. A feasible interpretation of the problem is given.

A vertex @h in a subset X of vertices of an undirected graph is redundant if its closed neighborhood is contained in the union of closed neighborhoods of vertices of X-{@h}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X-{@h}. The irredundance number ir(G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. In this note we show that ir(G) >= n/([email protected]) for a graph G having n vertices and maximum degree @D.

In this paper, we obtain necessary and sufficient conditions for a graph G not to have an M-alternating path between two vertices in G.

The center of a graph G is defined as subgraph of G induced by the set of vertices which have minimal eccentricities (i.e., minimal value of distance to the most distant vertices of G). It has been shown that only a finite number of graphs can be centers of maximal outerplanar graphs (mops). We generalize this result for the class of 2-trees which contains mops.

We show that every 2-connected triangulated planar graph with n vertices has a simple cycle C of length at most 2√2 · n which separates the interior vertices A from the exterior vertices B such that neither A nor B contain more than 2 3n vertices. The method also gives a linear time sequential algorithm for finding this simple cycle and an NC parallel algorithm. In general, if the maximum face size is d then we exhibit a cycle C as above of size at most 2√ d · n .

Suppose G is a fixed finite connected graph and for any two vertices x and y in G, dG(x,y) denotes the distance in G between x and y, i.e., the number of edges in a shortest path connecting x and y. Given an infinite sequence Q = (q1,q2,…) of vertices in G, suppose we would like to find another sequence P = PQ = (p0,p1,…) of vertices so that the quantity v ( P ) = lim sup n → ∞ 1 N ( ∑ i = 1 N ( d ( p i - 1 , p i ) + d ( p i , q i ) ) ) is as small as possible. This question represents a general formulation of a class of problems arising in self-adjusting data structures. In this paper we will investigate this and a number of related graph searching problems, such as requiring ***pn to be chosen before qn+i, i ≥ k, is known, and show how a number of interesting structural and algorithmic concepts from graph theory come together rather naturally, e.g., isometric embedding, Steiner points in graphs, retracts, diameters and linear programming.

This chapter discusses separate coding of correlated sources. Separate encoding-decoding of the two component sources yields significantly worse codes of the joint source than joint encoding-decoding. Various theorems are proved. A directed graph is a finite set of points, called vertices, together with a set of ordered pairs of vertices called directed edges. The depth of the graph is the maximum vertex depth, that is, the length of the longest path in the graph. While a single-letter characterization always suggests some algorithm for numerical evaluation, this usually is too complex for actual computation. Thus, it happens quite often that a single-letter characterization solves a problem only in a theoretical sense. The multiple-access channels are discussed. One can define achievable rate vectors and capacity region of a channel network also by using maximum probabilities of error rather than average ones. The so obtained capacity region will be called the m -capacity region.

The distance sequence of a vertex x of a graph is (d i (x)) n 1 where d i (x) is the number of vertices at distance i from x. The paper investigates under what condition it is true that almost every graph of a probability space is such that its vertices are uniquely determined by an initial segment of the distance sequence. In particular, it is shown that for r ≥ 3 and ɛ > O almost every labelled r-regular graph is such that every vertex x is uniquely determined by (d i (x)) u 1 , where u = ⌊ ( 1 2 + ɛ ) log n log ( r - 1 ) ⌋ . Furthermore, the paper contains an entirely combinatorial proof of a theorem of Wright [10] about the number of unlabelled graphs of a given size.

The k-eccentricity evaluated at a point x of a graph G is the sum of the (weighted) distances from x to the k vertices farthest from it. The k-centrum is the set of vertices for which the k-eccentricity is a minimum. The concept of k-centrum includes, as a particular case, that of center and that of centroid (or median) of a graph. The absolute k-centrum is the set of points (not necessarily vertices) for which the k-eccentricity is a minimum. In this paper it will be proven that, for a weighted tree, both deterministic and probabilistic, the k-eccentricity is a convex function and that the absolute k-centrum is a connected set and is contained in an elementary path. Hints will be given for the construction of an algorithm to find the k-centrum and the absolute k-centrum.

This paper is concerned with theκ-centrum of a graph. This concept, related to a particular location problem, generalizes that of the center and that of the median of a graph: theκ-centrum is the set of points for which the sum of the (weighted) distances from theκ farthest vertices is minimized. The paper will review some recent results about this problem. In particular, some properties of cardinality, connectivity and, more generally, of the structure of theκ-centrum of a weighted tree will be presented.

A stratum S k of a rooted tree is a set of vertices whose distance from the root is equal to k . We shall derive exact and asymptotic formulas for the expected value A r (n, k) of the number of vertices of degree r in S k of a random recursive tree with n vertices.

Minimizing the area of a circuit is an important problem in the domain of Very Large Scale Integration. We use a theoretical VLSI model to reduce this problem to one of laying out a graph, where the transistors and wires of the circuit are identified with the vertices and edges of the graph. We give an algorithm that produces VLSI layouts for classes of graphs that have good separator theorems. We show in particular that any planar graph of n vertices has an O(n lg2 n) area layout and that any tree of n vertices can be laid out in linear area. The algorithm maintains a sparse representation for layouts that is based on the well-known UNION-FIND data structure, and as a result, the running time devoted to bookkeeping is nearly linear.

Publisher Summary This chapter presents the theory of recurrence relations. The tower of Hanoi puzzle, for example, involved the recurrence relation Sn+1 = 2Sn + 1. In this situation, the recurrence relation related the minimum number of moves required to transfer a tower of n + 1 rings in the puzzle to the minimum number of moves required to transfer a tower of n rings. The chapter also presents the difference methods. It present the introduction of some of the basic definitions and ideas of the subject called finite differences, and indicate how these ideas may be used to solve recurrence relations. The chapter presents the problem of finding the chromatic polynomial of a map or of its corresponding graph. The empty graph with n vertices is defined to be the graph with n vertices and no edges. The complete graph on n vertices is defined to be the graph on n vertices in which each pair of vertices is joined by an edge. A graph G is connected if there is a path joining every pair of distinct vertices in G.

Let be G = (V,E) an arbitrary finite graph, where E is the set of edges and V= {vk}k=1n the set of n vertices numbered from 1 to n in an arbitrary order. We write (vk,v1) = ek1∈E if the vertices vk,v1∈V are connected by an edge otherwise ek1∉E.

The metric polytope MP n is defined by the triangle inequalities: x ij − x ik − x jk ⩽ 0 and x ij + x ik + x jk ⩽ 2 for all triples i, j, k of (1, …, n). The integral vertices of MP n are the incidence vectors of the cuts of the complete graph K n . Therefore, MP n is a relaxation of the cut polytope of K n . We study here the fractional vertices of MP n . Many of them are constructed from graphs; this is the case for the one-third-integral vertices. One-third-integral vertices are, in a sense, the simplest fractional vertices of MP n as MP n has no half-integral vertices. Several constructions for one-third-integral vertices are presented. In particular, the graphic vertices arising from the suspension of a tree are characterized. We describe the symmetries of MP n , and obtain that the vertices are partitioned into switching classes. With the exception of the cuts which are pairwise adjacent, it is shown that no two vertices of the same switching class are adjacent on MP n . The question of adjacency of the fractional vertices to the integral ones is also addressed. All the vertices of MP n for n ⩽ 6 are described.

Given two sets of vertices in a graph, it is often of a great interest to find out how these vertices are connected, especially to identify the vertices of high prominence defined on the topological structure. In this work, we formally define a V ertex S et B onding query (shorted as VSB), which returns a minimum set of vertices with the maximum importance w.r.t total betweenness and shortest path reachability in connecting two sets of input vertices. We find that such a kind of query is representative and could be widely applied in many real world scenarios, e.g., logistic planning, social community bonding and etc. Challenges are that many of such applications are constructed on graphs that are too large to fit in single server, and the VSB query evaluation turns to be NP-hard. To cope with the scalability issue and return the near optimal result in almost real time, we propose a generic solution framework on a shared nothing distributed environment. With the development of two novel techniques, guided graph exploration and betweenness ranking on exploration, we are able to efficiently evaluate queries for error bounded results with bounded space cost. We demonstrate the effectiveness of our solution with extensive experiments over both real and synthetic large graphs on the Google's Cloud platform. Comparing to the exploration only baseline method, our method achieves several times of speedup.

Let G = (V,E) denote an undirected weighted graph of n nodes and m edges, and let U ⊆ V. The relative eccentricity of a node v ∈ U is the maximum distance in G between v and any other node of U, while the radius of U in G is the minimum relative eccentricity of all the nodes in U. Several facility location problems ask for partitioning the nodes of G so as to minimize some global optimization function of the radii of the subsets of the partition. Here, we focus on the problem of partitioning the nodes of G into exactly p ≥ 2 non-empty subsets, so as to minimize the sum of the subset radii, called the total radius of the partition. This problem can be easily seen to be NP-hard when p is part of the input, but when p is fixed it can be solved in polynomial time by reducing it to a similar partitioning problem. In this paper, we first present an efficient O(n3) time algorithm for the notable case p = 2, which improves the O(mn2 + n3 log n) running time obtainable by applying the aforementioned reduction. Then, in an effort of characterizing meaningful polynomial-time solvable instances of the problem when p is part of the input, we show that (i) when G is a tree, then the problem can be solved in O(n3p3) time, and (ii) when G has bounded treewidth h, then the problem can be solved in O(n4h+4p3) time.

A three-dimensional {\em grid drawing} of a graph $G$ is a placement of the vertices at distinct integer points so that the straight-line segments representing the edges of $G$ are pairwise non-crossing. It is shown that for any fixed $r\geq 2$, every $r$-colorable graph of $n$ vertices has a three-dimensional grid drawing that fits into a box of volume $O(n^2)$. The order of magnitude of this bound cannot be improved.

An m-center set of a graph is any set of m points, belonging either to the edges or vertices, that minimizes the maximum distance from a vertex to its nearest m-center. This paper presents a method for solving the m-center problem by solving a finite series of minimum set covering problems.