An algorithm is constructed for recognizing the circulant graphs and finding a canonical labeling for them in polynomialtime. This algorithm also yields a cycle base of an arbitrary solvable permutation group. The co...
详细信息
Consider n independent jobs and m identical machines in parallel. Job j has a processing time p(j) and a deadline (d) over bar (j). It must complete its processing before or at its deadline. All jobs are available for...
详细信息
Consider n independent jobs and m identical machines in parallel. Job j has a processing time p(j) and a deadline (d) over bar (j). It must complete its processing before or at its deadline. All jobs are available for processing at time t = 0 and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines;such a schedule is called a feasible schedule. Given a feasible set of jobs, our goal is to find a schedule that minimizes the total completion time SigmaC(j). In the classical alpha|beta|gamma scheduling notation this problem is referred to as P|prmt, (d) over bar (j)\SigmaC(j). Lawler (Recent Results in the Theory of Machine Scheduling, in Mathematical Programming: The State of the Art, A. Bachem, M. Grotschel, and B. Korte, eds., Springer, Berlin, 1982, pp. 202 - 234) raised the question of whether or not the problem is NP-hard. In this paper we present a polynomial-time algorithm for every m greater than or equal to 2, and we show that the more general problem with m unrelated machines, i.e., R | prmt, (d) over bar (j)\SigmaC(j), is strongly NP-hard.
Given are two graphs H-1 = (V, E-1) and H-2 = (V, E-2) on the same vertex set. The line bigraph is the bipartite graph with the disjoint union of E-1 and E-2 as vertex set, and an edge between e(1) is an element of E-...
详细信息
Given are two graphs H-1 = (V, E-1) and H-2 = (V, E-2) on the same vertex set. The line bigraph is the bipartite graph with the disjoint union of E-1 and E-2 as vertex set, and an edge between e(1) is an element of E-1 and e(2) is an element of E-2 if the edges have some common vertex in V. We first show that the problem to determine whether a given bipartite graph is the line bigraph of two such graphs is NP-complete. We then present two special cases where the question can be solved in polynomialtime. A C-4-free bipartite graph is a line bigraph if and only if each component of the graph obtained by removing all degree-2 vertices has at most one cycle. Using the intersection multigraph of the set of all large bicliques, we then show that there is an efficient recognition algorithm for recognizing line bigraphs of two graphs both having minimum degree at least 3. (C) 2002 Elsevier Science B.V. All rights reserved.
An induced matching in a graph G is a set of edges, no two of which meet a common vertex or are joined by an edge of G;that is, an induced matching is a matching which forms an induced subgraph. It is known that findi...
详细信息
An induced matching in a graph G is a set of edges, no two of which meet a common vertex or are joined by an edge of G;that is, an induced matching is a matching which forms an induced subgraph. It is known that finding an induced matching of maximum cardinality in a graph is NP-hard. We show that a maximum induced matching in a weakly chordal graph can be found in polynomialtime. This generalizes previously known results for the induced matching problem. This also demonstrates that the maximum induced matching problem in chordal bipartite graphs can be solved in polynomialtime while the problem is known to be NP-hard for bipartite graphs in general. (C) 2003 Elsevier Science B.V. All rights reserved.
The present paper deals with the computational complexity of the discrete inverse problem of reconstructing finite point sets and more general functionals with finite support that are accessible only through some of t...
详细信息
The present paper deals with the computational complexity of the discrete inverse problem of reconstructing finite point sets and more general functionals with finite support that are accessible only through some of the values of their discrete Radon transform. It turns out that this task behaves quite differently from its well-studied companion problem involving 1-dimensional X-rays. Concentrating on the case of coordinate hyperplanes in R-d and on functionals psi : Z(d) --> D with D is an element of {{0, 1,...,r}, N-0} for some arbitrary but fixed r, we show in particular that the problem can be solved in polynomialtime if information is available for m such hyperplanes when m less than or equal to d - 1 but is NP-hard for m = d and D = {0, 1,...,r}. However, for D = N-0, a case that is relevant in the context of contingency tables, the problem is still in P. Similar results are given for the task of determining the uniqueness of a given solution and for a related counting problem. (C) 2002 Elsevier Science B.V. All rights reserved.
We are interested in the reconstruction of a domino tiling of a rectangle from its two orthogonal projections. We give polynomialalgorithms for some subproblems when all the dominoes are of the same type and prove NP...
详细信息
We are interested in the reconstruction of a domino tiling of a rectangle from its two orthogonal projections. We give polynomialalgorithms for some subproblems when all the dominoes are of the same type and prove NP-completeness results when there are three types of dominoes. When two types of dominoes are allowed. we give a polynomial-time transformation from a well-known open problem. (C) 2001 Elsevier Science B.V. All rights reserved.
Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the computational complexity of the segmentation prob...
详细信息
Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the computational complexity of the segmentation problem, assuming that the sought object forms a connected region in an intensity image. We show that the optimization problem of separating a connected region in a grid of M x N pixels is NP-hard under the interclass variance, a criterion that is often used in discriminant analysis. More importantly, we consider the basic case in which the object is bounded by two x-monotone curves (i.e., the object itself is x-monotone), and present polynomial-time algorithms for computing the optimal segmentation. Our main algorithm for exact optimal segmentation by two x-monotone curves runs in O(N-4) time;this algorithm is based on several techniques such as a parametric optimization formulation, a hand-probing algorithm for the convex hull of an unknown planar point set, and dynamic programming using fast matrix searching. Our efficient approximation scheme obtains an epsilon -approximate solution in O(epsilon N--1(2) log L) time, where epsilon is any fixed constant with 1 > epsilon > 0, and L is the total sum of the absolute values of the brightness levels of the image.
A subset of edges J subset of or equal to E(G) in a undirected graph G is called a join if at most half the edges of each cycle of G are contained in J. In this paper we consider the problem of finding a join of maxim...
详细信息
A subset of edges J subset of or equal to E(G) in a undirected graph G is called a join if at most half the edges of each cycle of G are contained in J. In this paper we consider the problem of finding a join of maximum weight: given a graph G and an edge weighting c:E(G) --> R, find a join of maximum weight. We show that the problem is NP-hard even in the case of 0, 1-weights, which answers a question of A. Frank in the negative. We also show that in the case of series-parallel graphs and arbitrary weights, the problem can be solved in time 0(n(3)), where n is the number of vertices in G. (C) 2001 Elsevier Science B.V. All rights reserved.
In this paper, we study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NIP-complete when the number of prescribed directions is greater than two...
详细信息
In this paper, we study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NIP-complete when the number of prescribed directions is greater than two. We provide a polynomial-time algorithm for reconstructing an interesting subclass of lattice sets (having some connectivity properties) from its X-rays in directions (1, 0), (0, 1) and (1, 1). This algorithm can be easily extended to contexts having more than three X-rays. (C) 2001 Elsevier Science B.V. All rights reserved.
This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by...
详细信息
This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a single server onto the relevant machine. The paper considers a number of classical scheduling objectives in this environment, under a variety of assumptions about setup and processing times. For each problem considered, the intention is to provide either a polynomial- or pseudo-polynomial-time algorithm, or a proof of binary or unary NP-completeness;The results provide a mapping of the computational complexity of these problems. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论