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.
The complexity of group testing is a long-standing open problem. Recently, Du and Ko studied some related problems which can explain the hardness of group testing undirectly. One of such problems is called the determi...
详细信息
The complexity of group testing is a long-standing open problem. Recently, Du and Ko studied some related problems which can explain the hardness of group testing undirectly. One of such problems is called the determinacy problem on which they left open questions for some models. In this paper, we answer all of them.
In this paper we study a class of quadratic maximization problems and their semidefinite programming (SDP) relaxation, For a special subclass: of dir problems we show that the SDP relaxation provides an exact optimal ...
详细信息
In this paper we study a class of quadratic maximization problems and their semidefinite programming (SDP) relaxation, For a special subclass: of dir problems we show that the SDP relaxation provides an exact optimal solution, Another subclass, which is NP-hard. guarantees that the SDP relaxation yields an approximate solution with a worst-case performance ratio of 0.87856.... This is a generalization of the well-known result uf Goemans and Williamson fur the maximum-cut problem. Finally, we discuss extensions of these results in the presence of a certain type of sign restrictions.
In this paper, we define a class of graphs which are referred to as (3, 1) graphs. A graph is a member of this class if it has the property that within each set of three vertices, there is at least one edge. We derive...
详细信息
In this paper, we define a class of graphs which are referred to as (3, 1) graphs. A graph is a member of this class if it has the property that within each set of three vertices, there is at least one edge. We derive a lower bound for the size of a maximum clique in a (3, 1) graph as well as an upper bound for the size of a minimum clique covering. In addition, we show that there exists a linear algorithm for constructing a Hamiltonian circuit in a connected (3, 1) graph and an n4-algorithm for finding a minimum coloring in a (3, 1) graph.
We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classe...
详细信息
We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs. (C) 2008 Elsevier B.V. All rights reserved.
We study the Student-Project Allocation problem with lecturer preferences over Projects (SPA-P). In this context it is known that stable matchings can have different sizes and the problem of finding a maximum size sta...
详细信息
We study the Student-Project Allocation problem with lecturer preferences over Projects (SPA-P). In this context it is known that stable matchings can have different sizes and the problem of finding a maximum size stable matching is NP-hard. There are two known approximation algorithms for MAX-SPA-P, with performance guarantees 2 and 32 . We show that MAX-SPA-P is polynomial-time solvable if there is only one lecturer involved, and NP-hard to approximate within some constant c > 1 if there are two lecturers involved. We also show that this problem remains NP-hard if each preference list is of length at most 3, with an arbitrary number of lecturers. We then describe an Integer Programming (IP) model to enable MAX-SPA-P to be solved optimally in the general case. Following this, we present results arising from an empirical evaluation that investigates how the solutions produced by the approximation algorithms compare to optimal solutions obtained from the IP model, with respect to the size of the stable matchings constructed, on instances that are both randomly-generated and derived from real datasets. (c) 2020 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
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.
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.
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.
Recently, increasing penetration of renewable energy generation has created challenges for power system operators to perform efficient power generation daily scheduling, due to the intermittent nature of the renewable...
详细信息
Recently, increasing penetration of renewable energy generation has created challenges for power system operators to perform efficient power generation daily scheduling, due to the intermittent nature of the renewable generation and discrete decisions of each generation unit. Among all aspects to be considered, a unit commitment polytope is fundamental and embedded in the models at different stages of power system planning and operations. In this article, we focus on deriving polynomial-time algorithms for the unit commitment problems with a general convex cost function and piecewise linear cost function, respectively. We refine an O(T-3) time, where T represents the number of time periods, algorithm for the deterministic single-generator unit commitment problem with a general convex cost function and accordingly develop an extended formulation in a higher-dimensional space that can provide an integral solution, in which the physical meanings of the decision variables are described. This means the original problem can be solved as a convex program instead of a mixed-integer convex program. Furthermore, for the case in which the cost function is piecewise linear, by exploring the optimality conditions, we derive more efficient algorithms for both deterministic (i.e., O(T) time) and stochastic (i.e., O(N) time, where N represents the number of nodes in the stochastic scenario tree) single-generator unit commitment problems. We also develop the corresponding extended formulations for both deterministic and stochastic single-generator unit commitment problems that solve the originalmixed-integer linear programs as linear programs. Similarly, physical meanings of the decision variables are explored to show the insights of the new modeling approach.
暂无评论