For an integer t, we let P t denote the t-vertex path. We write H + G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that ...
详细信息
For an integer t, we let P t denote the t-vertex path. We write H + G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph G is H-free if no induced subgraph of G is isomorphic to the graph H. In this paper, we study the complexity of k-coloring, for a fixed integer k, when restricted to the class of H-free graphs with a fixed graph H. We provide a polynomial-time algorithm to test if, for fixed r, a (P-6 + rP(3))-free is three-colorable, and find a coloring if one exists. We also solve the list version of this problem, where each vertex is assigned a list of possible colors, which is a subset of {1, 2, 3}. This generalizes results of Broersma, Golovach, Paulusma, and Song, and results of Klimosova, Malik, Masarik, Novotna, Paulusma, and Slivova. Our proof uses a result of Ding, Seymour, and Winkler relating matchings and hitting sets in hypergraphs. We also prove that the problem of deciding if a (P 5 + P 2)-free graph has a k-coloring is NP-hard for every fixed k >= 5.
The complexity status of the stable set problem in the class of P-5-free graphs is unknown. In the present paper we study an approach to the problem based on finding augmenting graphs. The main result is that the stab...
详细信息
The complexity status of the stable set problem in the class of P-5-free graphs is unknown. In the present paper we study an approach to the problem based on finding augmenting graphs. The main result is that the stable set problem in the class of P-5-free graphs is polynomially equivalent to the problem of finding augmenting graphs containing a P-4. We apply this result to detect a new infinite family of graph classes where the problem has a polynomial time solution. The new family generalizes several previously known results. (C) 2003 Elsevier B.V. All rights reserved.
A skew star is a tree with exactly three vertices of degree one being at distance 1, 2, 3 from the only vertex of degree three. In the present paper, we propose a structural characterization for the class of bipartite...
详细信息
A skew star is a tree with exactly three vertices of degree one being at distance 1, 2, 3 from the only vertex of degree three. In the present paper, we propose a structural characterization for the class of bipartite graphs containing no skew star as an induced subgraph and discuss some applications of the obtained result. (C) 2002 Elsevier Science B.V. All rights reserved.
In this paper we consider the edge ranking problem of weighted trees. We prove that a special instance of this problem, namely edge ranking Of multitrees is NP-hard already for multitrees with diameter at most 10. Not...
详细信息
In this paper we consider the edge ranking problem of weighted trees. We prove that a special instance of this problem, namely edge ranking Of multitrees is NP-hard already for multitrees with diameter at most 10. Note that the same problem but for trees is linearly solvable. We give an O(log n)-approximation polynomial time algorithm for edge ranking of weighted trees. (c) 2005 Elsevier B.V. All rights reserved.
We consider a problem of finding a point in the intersection of n balls in the Euclidean space E-m. For the case m = 2 we suggest two algorithms of the complexity O(n(2) log n) and O(n(3)) operations, respectively. Fo...
详细信息
We consider a problem of finding a point in the intersection of n balls in the Euclidean space E-m. For the case m = 2 we suggest two algorithms of the complexity O(n(2) log n) and O(n(3)) operations, respectively. For the general case we suggest an exact polynomial recursive algorithm which uses the orthogonal transformation of the space E-m.
We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted ty...
详细信息
We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted type of P(3)-partition of the graph G. A necessary condition (*) is described and some classes of graphs are identified where the search problem of finding a feasible P(3)-partition is polynomially solvable and, in addition, (*) is not only necessary but also sufficient for the existence of a P(3)-partition. It is also proved that the decision problem on two particular graph classes - defined in terms of forbidden subgraphs - remains NP-complete, but is polynomially solvable on the intersection of those two classes. The polynomial-time solvability of some further related problems is shown, too. (C) 2008 Elsevier B.V. All rights reserved.
The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable ...
详细信息
The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph with a designated root node and arc-costs , find a minimum cardinality subset H of the arc set A such that H intersects every minimum c-cost r-arborescence. By an r-arborescence we mean a spanning arborescence of root r. The algorithm we give solves a weighted version as well, in which a nonnegative weight function (unrelated to c) is also given, and we want to find a subset H of the arc set such that H intersects every minimum c-cost r-arborescence, and is minimum. The running time of the algorithm is , where n and m denote the number of nodes and arcs of the input digraph, and T(n, m) is the time needed for a minimum cut computation in this digraph. A polyhedral description is not given, and seems rather challenging.
This paper considers the existence and uniqueness of interval strong solutions of interval systems of max-plus linear equations. A necessary and sufficient condition for the existence of interval strong solutions is p...
详细信息
This paper considers the existence and uniqueness of interval strong solutions of interval systems of max-plus linear equations. A necessary and sufficient condition for the existence of interval strong solutions is presented. The proof of the existence of interval strong solutions is constructive and results in a formula for computing such solutions. A necessary and sufficient condition for the uniqueness of interval strong solutions is established by testing the unique solvability of a finite number of subsystems rather than all subsystems. On this basis, a polynomial algorithm is developed to verify the uniqueness of interval strong solutions. (C) 2017 Elsevier Inc. All rights reserved.
We consider project scheduling where the project manager's objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the probl...
详细信息
We consider project scheduling where the project manager's objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the problem identifying both polynomially solvable and NP-hard versions of the problem. The complexity of the problem is seen to be dependent on the nature of renewable resource constraints, precedence constraints, and the ability to crash activities in the project. (C) 2014 Elsevier B.V. All rights reserved.
We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of t...
详细信息
We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges;we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. (C) 1999 John Wiley & Sons, Inc.
暂无评论