Given a graph G, a spanning subgraph H of G is a t-spanner if for every edge xy of G, the distance in H between x and y is at most t. Spanners have applications in communication networks, distributed systems, parallel...
详细信息
Given a graph G, a spanning subgraph H of G is a t-spanner if for every edge xy of G, the distance in H between x and y is at most t. Spanners have applications in communication networks, distributed systems, parallel computation, and other areas. This paper is concerned with the complexity of determining whether a graph contains a t-spanner whose maximum degree is at most Δ, where Δ, t≥2 are fixed integers. The problem is shown to be NP-complete for any fixed Δ≥4 and t≥2, and linear for Δ=2 and any fixed t≥2. The problem for Δ=3 is open. Furthermore, if the t-spanner in the problem is required to be a tree, then the problem becomes linear. The problem also becomes linear when input graphs are partial k-trees for some fixed integer k.
This paper presents a linear algorithm for partitioning a biconnected graph into a pair of disjoint connected subgraphs, each of which contains a specific vertex and has a specific number of vertices.
This paper presents a linear algorithm for partitioning a biconnected graph into a pair of disjoint connected subgraphs, each of which contains a specific vertex and has a specific number of vertices.
As a model of certain location problem, we consider the following domination problem. The k-neighbor domination problem is to select a minimum cardinality vertex set D of a graph G = (V, E) such that every vertex x no...
详细信息
As a model of certain location problem, we consider the following domination problem. The k-neighbor domination problem is to select a minimum cardinality vertex set D of a graph G = (V, E) such that every vertex x not in D is adjacent to at least k vertices in D. This paper presents a linear algorithm to solve the problem for block graphs. For any fixed k, we also prove that the k-neighbor domination problem is NP-complete for some classes of graphs.
We consider the following weighted perfect domination problem. Suppose G = (V, E) is a graph in which every vertex x member of V has a cost c(x) and every edge e member of E has a cost c(e). The problem is to find a s...
详细信息
We consider the following weighted perfect domination problem. Suppose G = (V, E) is a graph in which every vertex x member of V has a cost c(x) and every edge e member of E has a cost c(e). The problem is to find a subset D included in V, such that every vertex not in D is adjacent to exactly one vertex in D, and its total cost c(D) = Sigma (c(x): x member of D) + Sigma (c(x, y): x member of / D, y member of D and (x, y) member of E) is minimum. We first prove that the (unweighted) perfect domination problem is NP-complete for biparticle graphs and chordal graphs. We then give a linear algorithm for the weighted perfect domination problem in trees.
A set of vertices D is a dominating set of a graph G=(V,E)<span style="display: inline-block; overflow: hidden; vertical-align: -0.352em; border-left: 0px solid; width: 0
Though linear algorithms for finding the convex hull of a simply-connected polygon have been reported, not all are short and correct. A compact version based on Sklansky"s original idea(7) and Bykat"s counte...
详细信息
Though linear algorithms for finding the convex hull of a simply-connected polygon have been reported, not all are short and correct. A compact version based on Sklansky"s original idea(7) and Bykat"s counter-example(8) is given. Its complexity and correctness are also shown.
A time algorithm is presented for the total domination problem in interval graphs. Gilmore and Hoffman (1964) showed that the maximal cliques of an interval graph can be linearly ordered. The algorithm proceeds by v...
详细信息
A time algorithm is presented for the total domination problem in interval graphs. Gilmore and Hoffman (1964) showed that the maximal cliques of an interval graph can be linearly ordered. The algorithm proceeds by visiting each clique in increasing order of height. After the clique C (subscript i) has been visited, a set D (subscript i) is found. Induction on the number of cliques shows that D (subscript i) is the minimum total dominating set of the set comprised of vertices in the graph that are no greater than i in level, and D (subscript i) is of maximum span and range. Farber (1984) developed a polynomial time algorithm for finding the minimum dominating set of a strongly chordal graph, which might lead to the expectation that the total domination problem on strongly chordal graphs would be polynomial also. However, the algorithm for interval graphs presented does not seem to be extendable to strongly chordal graphs.
A linear time algorithm for the Hamiltonian circuit problem in interval graphs is presented. The maximal cliques of an interval graph can be linearly ordered, such that, for every vertex of the graphs, the maximal cl...
详细信息
A linear time algorithm for the Hamiltonian circuit problem in interval graphs is presented. The maximal cliques of an interval graph can be linearly ordered, such that, for every vertex of the graphs, the maximal cliques containing the vertex take place consecutively. The algorithm will construct a Hamiltonian circuit, if there is one, by growing a path of labeled vertices. The vertices are initially unlabeled. The algorithm visits the cliques in increasing order of height. The algorithm runs in linear time as each of the steps is linear in either the size of the graph, the number of cliques of the graph, or in the size of a clique. The correctness of the algorithm is derived from the theorem that, if the algorithm reaches the final clique, a Hamiltonian circuit for the graph has been found, otherwise the algorithm has reported that there is no Hamiltonian circuit for the graph.
A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating...
详细信息
暂无评论