A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.     

The algorithmic complexity of mixed domination in graphs

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.     

How to Use Spanning Trees to Navigate in Graphs

In this paper, we investigate three strategies of how to use a spanning tree T of a graph G to navigate in G, i.e., to move from a current vertex x towards a destination vertex y via a path that is close to optimal. In each strategy, each vertex v has full knowledge of its neighborhood N _G [v] in G (or, k-neighborhood D _k (v,G), where k is a small integer) and uses a small piece of global information from spanning tree T (e.g., distance or ancestry information in T), available locally at v, to navigate in G. We investigate advantages and limitations of these strategies on particular families of graphs such as graphs with locally connected spanning trees, graphs with bounded length of largest induced cycle, graphs with bounded tree-length, graphs with bounded hyperbolicity. For most of these families of graphs, the ancestry information from a Breadth-First-Search-tree guarantees short enough routing paths. In many cases, the obtained results are optimal up to a constant factor.     

On the bi-enhancement of chordal-bipartite probe graphs

Given a class C of graphs, a graph G=(V,E) is said to be a C-probe graph if there exists a stable (i.e., independent) set of vertices X⊆V and a set F of pairs of vertices of X such that the graph G^′=(V,E∪F) is in the class C. Recently, there has been increasing interest and research on a variety of C-probe graph classes, such as interval probe graphs, chordal probe graphs and chain probe graphs.In this paper we focus on chordal-bipartite probe graphs. We prove a structural result that if B is a bipartite graph with no chordless cycle of length strictly greater than 6, then B is chordal-bipartite probe if and only if a certain “enhanced” graph B^∗ is a chordal-bipartite graph. This theorem is analogous to a result on interval probe graphs in Zhang (1994) [18] and to one on chordal probe graphs in Golumbic and Lipshteyn (2004) [11].     

The edge-orientation problem and some of its variants on weighted graphs

Let G(V, E) be a connected undirected graph with n vertices and m edges, where each vertex v is associated with a cost C(v) and each edge e = (u, v) is associated with two weights, W(u → v) and W(v → u). The issue of assigning an orientation to each edge so that G becomes a directed graph is resolved in this paper. Determining a scheme to assign orientations of all edges such that max_x∈V{C(x)+∑_x→zW(x→z)} is minimized is the objective. This issue is called the edge-orientation problem (the EOP). Two variants of the EOP, the Out-Degree-EOP and the Vertex-Weighted EOP, are first proposed and then efficient algorithms for solving them on general graphs are designed. Ascertaining that the EOP is NP-hard on bipartite graphs and chordal graphs is the second result. Finally, an O(n log n)-time algorithm for the EOP on trees is designed. In general, the algorithmic results in this paper facilitate the implementation of the weighted fair queuing (WFQ) on real networks. The objective of the WFQ is to assign an effective weight for each flow to enhance link utilization. Our findings consequently can be easily extended to other classes of graphs, such as cactus graphs, block graphs, and interval graphs.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

A linear-time algorithm for paired-domination problem in strongly chordal graphs

Let G=(V,E) be a simple graph without isolated vertices. A vertex set S⊆V is a paired-dominating set if every vertex in V−S has at least one neighbor in S and the induced subgraph G[S] has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.     

Structure and linear time recognition of 3-leaf powers

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is the k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos motivated by the search for underlying phylogenetic trees. Their results imply a O(n³) time recognition algorithm for 3-leaf powers. Later, Dom, Guo, Hüffner, and Niedermeier characterized 3-leaf powers as the (bull, dart, gem)-free chordal graphs. We show that a connected graph is a 3-leaf power if and only if it results from substituting cliques into the vertices of a tree. This characterization is much simpler than the previous characterizations via critical cliques and forbidden induced subgraphs and also leads to linear time recognition of these graphs.     

The cable trench problem: combining the shortest path and minimum spanning tree problems

Let G=(V,E) be a connected graph with specified vertex v₀∈V, length l(e)⩾0 for each e∈E, and positive parameters τ and γ. The cable-trench problem (CTP) is to find a spanning tree T such that τl_τ(T)+γl_γ(T) is minimized where l_τ(T) is the total length of the spanning tree T and l_γ(T) is the total path length in T from v₀ to all other vertices of V. Since all vertices must be connected to v₀ and only edges from E are allowed, the solution will not be a Steiner tree. Consider the ratio R=τ/γ. For R large enough the solution will be a minimum spanning tree and for R small enough the solution will be a shortest path. In this paper, the CTP will be shown to be NP-complete. A mathematical formulation for the CTP will be provided for specific values of τ and γ. Also, a heuristic will be discussed that will solve the CTP for all values of R.Scope and purposeBoth the shortest path and the minimum spanning tree problems are universally discussed in operations research and management science textbooks. Since the late 1950s, efficient algorithms have been known for both of these problems. In this paper, the cable-trench problem is defined which combines the shortest path problem and the minimum spanning tree problem to create a problem that is shown to be NP-complete. In other words, two easy problems are combined to get a more realistic problem that is difficult to solve. Examples are used to illustrate an efficient and effective heuristic solution procedure for the cable-trench problem.