MINIMUM DOMINATING SET OF QUEENS is one of the typical programming exercises of a first year's computer science course. However, little work has been published on the complexity of this problem. We analyse here se...
详细信息
MINIMUM DOMINATING SET OF QUEENS is one of the typical programming exercises of a first year's computer science course. However, little work has been published on the complexity of this problem. We analyse here several algorithms and show that advanced algorithmic techniques may dramatically speed up solving this problem. (C) 2009 Elsevier B.V. All rights reserved.
We consider the problem of scheduling jobs with equal lengths on uniform parallel batch machines with non-identical capacities where each job can only be processed on a specified subset of machines called its processi...
详细信息
We consider the problem of scheduling jobs with equal lengths on uniform parallel batch machines with non-identical capacities where each job can only be processed on a specified subset of machines called its processing set. For the case of equal release times, we give efficient exact algorithms for various objective functions. For the case of unequal release times, we give efficient exact algorithms for minimizing makespan.
We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a ...
详细信息
We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.
We consider an interval scheduling problem where n jobs are required to be carried out by m nonidentical machines in an offline-scheduling way. Each job has a starting time, a finishing time and a number of processing...
详细信息
We consider an interval scheduling problem where n jobs are required to be carried out by m nonidentical machines in an offline-scheduling way. Each job has a starting time, a finishing time and a number of processing units. Every machine has different number of processing units to carry out jobs. A machine can process only one job at a time without interrupted on the condition that the number of its units must satisfy job's requirement. Further more, all units in one machine consume energy if the machine is powered up. Within this setting, one is asked to find a proper schedule of machines so that the total number of working units is as less as possible. For this interval scheduling problem, we first discuss an exact method based on integer programming which can be solved by branch-and-bound algorithm. Then, we propose two approximated methods named GreedyBS and GreedyMR using greedy strategy. GreedyBS is proved to be a 2.1343-approximated algorithm. All proposed algorithms are tested on a large set of randomly generated instances. It turns out that GreedyBS requires less total units of machines under time constrain when comparing with GreedyMR and exact methods in most cases, while GreedyMR costs the minimum time. Several parameters of GreedyBS and GreedyMR were also evaluated to improve the performances of these two algorithms.
This paper proposes a new matrix-based project planning method that takes into consideration task importance or probability of completions thus determines and ranks the importance or probability of possible project sc...
详细信息
This paper proposes a new matrix-based project planning method that takes into consideration task importance or probability of completions thus determines and ranks the importance or probability of possible project scenarios and project structures. The proposed algorithm is fast, aims to select the most important project scenarios or the least cost/time demanding project structures. The algorithm is generic, can host several types of goals dictated by the characteristics of project management and as such can be the fundamental element of a project expert- and decision-making system. (C) 2015 Elsevier Ltd. All rights reserved.
We design fast exponential time algorithms for some intractable graph-theoretic problems. Our main result states that a minimum optional dominating set in a graph of order n can be found in time 0* (1.8899(n)). Our me...
详细信息
We design fast exponential time algorithms for some intractable graph-theoretic problems. Our main result states that a minimum optional dominating set in a graph of order n can be found in time 0* (1.8899(n)). Our methods to obtain this result involve matching techniques. The list of the considered problems includes MINIMUM MAXIMAL MATCHING, 3-COLOURABILITY, MINIMUM DOMINATING EDGE SET, MINIMUM CONNECTED DOMINATING SET (similar to MAXIMUM LEAF SPANNING TREE), MINIMUM INDEPENDENT DOMINATING SET and MINIMUM DOMINATING SET. (C) 2008 Elsevier B.V. All rights reserved.
We consider a two-dimensional problem in which one is required to split a given rectangular bin into the smallest number of items. The resulting items must be squares to be packed, without overlapping, into the bin so...
详细信息
We consider a two-dimensional problem in which one is required to split a given rectangular bin into the smallest number of items. The resulting items must be squares to be packed, without overlapping, into the bin so as to cover all the given rectangle. We present a mathematical model and a heuristic algorithm that is proved to find the optimal solution in some special cases. Then, we introduce a relaxation of the problem and present different exact approaches based on this relaxation. Finally, we report computational experiments on the performances of the algorithms on a large set of randomly generated instances.
We consider a scenario in which certain target locations are monitored through sensors, which are scattered all over a considered area. A quality-of-service threshold imposes that, at any given time, a predefined perc...
详细信息
We prove that the Hadwiger number of an n-vertex graph G (the maximum size of a clique minor in G) cannot be computed in time n(o(n)), unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known ope...
详细信息
We prove that the Hadwiger number of an n-vertex graph G (the maximum size of a clique minor in G) cannot be computed in time n(o(n)), unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of n(o(n))-time algorithms (up to the ETH) for a large class of computational problems concerning edge contractions in graphs.
Given a graph with weights on its vertices and blocking costs on its edges, and a user-defined threshold tau 0 the minimum cost edge blocker clique problem (EBCP) is introduced as the problem of blocking a minimum cos...
详细信息
Given a graph with weights on its vertices and blocking costs on its edges, and a user-defined threshold tau 0 the minimum cost edge blocker clique problem (EBCP) is introduced as the problem of blocking a minimum cost subset of edges so that each clique's weight is bounded above by tau Clusters composed of important actors with quick communications can be effectively modeled as large-weight cliques in real-world settings such as social, communication, and biological systems. Here, we prove that EBCP is NP-hard even when tau is a fixed parameter, and propose a combinatorial lower bound for its optimal objective. A class of inequalities that are valid for the set of feasible solution to EBCP is identified, and sufficient conditions for these inequalities to induce facets are presented. Using this class of inequalities, EBCP is formulated as a linear 0-1 program including potentially exponential number of constraints. We develop the first problem-specific branch-and-cut algorithm to solve EBCP, which utilizes the aforementioned constraints in a lazy manner. We also developed the first combinatorial branch-and-bound solution approach for this problem, which aims to handle large graph instances. Finally, computational results of solving EBCP on a collection of random graphs and power-law real-world networks by using our proposed exact algorithms are also provided.
暂无评论