This paper considers the Bicriteria Shortest Path Problem (BSP) with the two conflicting objectives, minimizing the transportation cost and the total travel time. Bicriteria Shortest Path Problems, are often NP-hard p...
详细信息
Many exact;algorithms for NP-hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing number of graph modifications, such as dele...
详细信息
ISBN:
(纸本)9783642145520
Many exact;algorithms for NP-hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing number of graph modifications, such as deletions, that reduce the problem instance and have to be "taken back" frequently during the search process. The use of efficient data structures is necessary for fast graph modification modules as well as fast take-back procedures. In this paper, we investigate practical implementation-based aspects of exact algorithms by providing a hybrid graph representation that addresses the take-back challenge and combines the advantage of O(1) adjacency-queries in adjacency-matrices with the advantage of efficient neighborhood traversal in adjacency-lists.
In the CONNECTED RED-BLUE DOMINATING SET problem we are given a graph C;whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset...
详细信息
ISBN:
(纸本)9783642130724
In the CONNECTED RED-BLUE DOMINATING SET problem we are given a graph C;whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset S of B such that each red vertex of (7 is adjacent to some vertex in S. The problem can be solved in O* (2(n-|B|)) time by reduction to the WEIGHTED STEINER TREE problem. Combining exhaustive enumeration when |B| is small with the WEIGHTED STEINER TREE approach when |B| is large, solves the problem in O*(1.4143(n)). In this paper we present a. first non-trivial exact algorithm whose running time is in O* (1.3645(n)). We use our algorithm to solve the CONNECTED DOMINATING SET problem in O* (1.8619(n)). This improves the current best known algorithm, which used sophisticated run-time analysis via the measure and conquer technique to solve the problem in O* (1.8966(n)).
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2(o(f(k)))p(n) time if and only if it is solvable in time O(2(delta f...
详细信息
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2(o(f(k)))p(n) time if and only if it is solvable in time O(2(delta f(k))q(n)) for any constant delta>0, where p and q are polynomials. We then illustrate how this equivalence can be used to show that special instances of parameterized NP-hard problems are as difficult as the general instances. For example, we show that the PLANAR DOMINATING SET problem on degree-3 graphs can be solved in 2(0(root k))p(n) parameterized time if and only if the general PLANAR DOMINATING SET problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well. (C) 2009 Elsevier B.V. All rights reserved.
In the literature of the combinatorial optimization problems, it is a commonplace to find more than one mathematical model for the same problem. The significance of a model may be measured in terms of the efficiency o...
详细信息
In the literature of the combinatorial optimization problems, it is a commonplace to find more than one mathematical model for the same problem. The significance of a model may be measured in terms of the efficiency of the solution algorithms that can be built upon it. The purpose of this article is to present a new network model for the well known combinatorial optimization problem-the job shop scheduling problem. The new network model has similar structure as the disjunctive graph model except that it uses permutations of jobs as decision variables instead of the binary decision variables associated with the disjunctive arcs. To assess the significance of the new model, the performances of exact branch-and-bound algorithmic implementations that are based on both the new model and the disjunctive graph model are compared. (C) 2008 Elsevier Inc. All rights reserved.
The Vehicle Routing Problem (VRP) was introduced 50 years ago by Dantzig and Ramser under the title "The Truck Dispatching Problem." The study of the VRP has given rise to major developments in the fields of...
详细信息
The Vehicle Routing Problem (VRP) was introduced 50 years ago by Dantzig and Ramser under the title "The Truck Dispatching Problem." The study of the VRP has given rise to major developments in the fields of exact algorithms and heuristics. In particular, highly sophisticated exact mathematical programming decomposition algorithms and powerful metaheuristics for the VRP have been put forward in recent years. The purpose of this article is to provide a brief account of this development.
The goal Of the CLUSTER EDITING problem is to make the fewest changes to the edge set of an input graph such that the resulting graph is a disjoint union Of cliques. This problem is NP-complete but recently, several p...
详细信息
The goal Of the CLUSTER EDITING problem is to make the fewest changes to the edge set of an input graph such that the resulting graph is a disjoint union Of cliques. This problem is NP-complete but recently, several parameterized algorithms have been proposed. In this paper, we present a number of surprisingly simple search tree algorithms for WEIGHTED CLUSTER EDITING assuming that edge insertion and deletion costs are positive integers. We show that the smallest search tree has size O(1.82(k)) for edit cost k, resulting in the currently fastest parameterized algorithm, both for this problem and its unweighted counterpart. We have implemented and compared our algorithms, and achieved promising results.(1) (C) 2009 Elsevier B.V. All rights reserved.
In 1990, Courcelle showed that every problem definable in Monadic Second-Order Logic (MSO) can be solved in linear time on graphs with bounded treewidth. This powerful and important theorem is amongst others the found...
详细信息
In 1990, Courcelle showed that every problem definable in Monadic Second-Order Logic (MSO) can be solved in linear time on graphs with bounded treewidth. This powerful and important theorem is amongst others the foundation for several fixed parameter tractability results. The standard proof of Courcelle's Theorem is to construct a finite bottom-up tree automaton that recognizes a tree decomposition of the graph. However, the size of the automaton, which is usually hidden as a constant in the Landau-notation, can become extremely large and cannot be bounded by any elemental function unless P = NP (Frick and Grohe, 2004). This makes the problem hard to tackle in practice, because it is just impossible to construct the tree automata. Aiming for a practical implementation, we give a proof of Courcelle's Theorem restricted to Extended MSO formulas of the form opt U subset of V phi( U), where phi is a first-order formula with vocabulary (adj, U) and opt is an element of{min, max}. Note that many optimization problems such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set can be expressed by such formulas. The proof uses a new technique based on using Hintikka game properties in dynamic programming. To demonstrate the usability of this approach, we present an implementation that solves such formulas on graphs with small pathwidth. It turns out that the large constants can be circumvented on graphs that are not too complex.
In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the mini...
详细信息
In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm. (C) 2009 Elsevier B.V. All rights reserved.
One of the most challenging problems in computational biology is the reconstruction of DNA sequences from DNA fragments. This paper describes the problems of sequencing by hybridization with standard, isothermic and m...
详细信息
ISBN:
(纸本)9781424429011
One of the most challenging problems in computational biology is the reconstruction of DNA sequences from DNA fragments. This paper describes the problems of sequencing by hybridization with standard, isothermic and multistage oligonucleotide libraries. However, the problems are NP-hard in the strong sense in case of errors. With the study of combinatorial optimization, it has become common for the researchers to apply the exact and heuristic algorithms, especially the latter, to solve these problems. Though there have been various available methods in the literature, researchers still have difficulties in choosing the best method that could solve these problems well. This paper aims to review the existing algorithms, compare them, point out the flaws of these works and indicate the emerging trend.
暂无评论