We study computational complexity of the maximum independent set problem on graphs of bounded vertex degree. In general, this problem is NP-hard. However, under certain restrictions it becomes polynomial-time solvable...
详细信息
ISBN:
(纸本)9780898716245
We study computational complexity of the maximum independent set problem on graphs of bounded vertex degree. In general, this problem is NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify three graph properties to which the complexity of the problem is sensible.
Given a graph G = (V, E), a set of vertices S subset of V covers v is an element of V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location proble...
详细信息
Given a graph G = (V, E), a set of vertices S subset of V covers v is an element of V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + n log n)-timealgorithm for k = 2, where n = \V\ and m = \E\. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-timealgorithm, which is an extension of the linear-timealgorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k - 1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.
We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective co...
详细信息
We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective coefficient vector c is an element of R-n are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x >= 0, can be solved in in O(n(2.5)c(A)) interior-point method iterations. Here 0 is the vector of all zeros and c(A) is the condition measure of matrix A defined in [25]. This complexity iteration bound is reduced by a factor n from that for general LP(A, b, c) in [ 25]. We also prove that the iteration bound will be further reduced to O(n(1.5)c(A)) for LP(A, 0, 0), i.e., for the homogeneous linear feasibility problem. These results are surprising since the classical view has been that linear feasibility would be as hard as linear programming.
A graph G is called a satgraph if there exists a partition A boolean OR B = V(G) such that A induces a clique [possibly, A = 0], B induces a matching [i.e., G(B) is a 1-regular subgraph, possibly, B = 0], and there ar...
详细信息
A graph G is called a satgraph if there exists a partition A boolean OR B = V(G) such that A induces a clique [possibly, A = 0], B induces a matching [i.e., G(B) is a 1-regular subgraph, possibly, B = 0], and there are no triangles (a, b, b'), where alpha epsilon A and b, b' epsilon B. We also introduce the hereditary closure of Y A J, denoted by H Y A J [hereditary satgraphs]. The class H Y A J contains split graphs. In turn, H Y A J is contained in the class of all (1, 2)-split graphs [A. Gyarfas, Generalized split graphs and Ramsey numbers, J. Combin. Theory Ser. A 81 (2) (1998) 255-261], the latter being still not charactefized. We characterize satgraphs in terms of forbidden induced subgraphs. There exist close connections between satgraphs and the satisfiability problem [SAT]. In fact, SAT is linear-time equivalent to finding the independent domination number in the corresponding satgraph. It follows that the independent domination problem is NP-complete for the hereditary satgraphs. In particular, it is NP-complete for perfect graphs. (c) 2005 Elsevier B.V. All rights reserved.
In this paper, the optimal design of reliability indices in an electrical distribution system and their impact to planning are studied. By formulating the cost due to interrupted KVA-hour, initial interruption cost, a...
详细信息
In this paper, the optimal design of reliability indices in an electrical distribution system and their impact to planning are studied. By formulating the cost due to interrupted KVA-hour, initial interruption cost, and modification cost in terms of component reliability indices, an optimization problem is derived while simultaneously considering multiple load points and feeder capacity limits, resulting in a nonlinear programming problem. To solve this nonlinear programming problem, an effective polynomial-time algorithm is presented. The numerical test shows that not only significant savings can be achieved, but also information on identifying value-saving feeder/components can be revealed as well. This is a valuable tool to distribution planning/operations. (C) 2003 Elsevier Science Ltd. All rights reserved.
An st-path is a path with the end-vertices s and t. An s-path is a path with an end-vertex s. The results of this paper include necessary and sufficient conditions for a (claw, net)-free graph G with s, t is an elemen...
详细信息
An st-path is a path with the end-vertices s and t. An s-path is a path with an end-vertex s. The results of this paper include necessary and sufficient conditions for a (claw, net)-free graph G with s, t is an element of V(G) and e is an element of E(G) to have (1) a Hamiltonian s-path, (2) a Hamiltonian st-path, (3) a Hamiltonian s- and st-paths containing e when G has connectivity one, and (4) a Hamiltonian cycle containing e when G is 2-connected. These results imply that a connected {claw, net}-free graph has a Hamiltonian path and a 2-connected {claw, net}-free graph has a Hamiltonian cycle [D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden subgraphs and the Hamiltonian theme, in: The Theory and Application of Graphs (Kalamazoo, Mich., 1980), Wiley, New York, 198 1, pp. 297-316]. Our proofs of (1)-(4) are shorter than the proofs of their corollaries in [D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden subgraphs and the Hamiltonian theme, in: The Theory and Application of Graphs (Kalamazoo, Mich., 1980), Wiley, New York, 1981, pp. 297-316], and provide polynomial-time algorithms for solving the corresponding Hamiltonicity problems. (c) 2006 Elsevier B.V. All rights reserved.
For the two-machine open shop sum-batch problem to minimize the makespan an optimal schedule is known to contain one, two or three batches on each machine, and finding a two-batch optimal schedule is NP-hard. We adapt...
详细信息
For the two-machine open shop sum-batch problem to minimize the makespan an optimal schedule is known to contain one, two or three batches on each machine, and finding a two-batch optimal schedule is NP-hard. We adapt the open shop algorithm by de Werra for finding a three-batch optimal schedule in linear time. (c) 2005 Elsevier B.V. All rights reserved.
We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes ...
详细信息
We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1, 2)-polar graphs. On the other hand, both problems can be solved in polynomialtime for (1, I)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (alpha, beta)-polar graphs and study the computational complexity of the problems on polar graphs of special types. (c) 2006 Elsevier B.V. All rights reserved.
Motivated by the development of an effcient and stable routing scheme for the Internet, Papadimitriou introduced a multicommodity ow game and raised the problem of whether the core of a multicommodity ow game is alway...
详细信息
ISBN:
(纸本)9781424403868
Motivated by the development of an effcient and stable routing scheme for the Internet, Papadimitriou introduced a multicommodity ow game and raised the problem of whether the core of a multicommodity ow game is always nonempty. Markakis and Saberi settled the problem affrmatively. However, thier proof is not constructive, and it is not known how to Ynd a solution in the core of the game, to the best of my knowledge. This paper presents a polynomial-time algorithm for nding pound a multicommodity ow game if G is a spider.
The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which ...
详细信息
ISBN:
(纸本)9780898716054
The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e. finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.
暂无评论