Chartrand, Haynes, Henning and Zhang introduced a variation of domination called stratified domination in graphs. This paper studies stratified domination from an algorithmic point of view. A 2-stratified (or black-wh...
详细信息
Chartrand, Haynes, Henning and Zhang introduced a variation of domination called stratified domination in graphs. This paper studies stratified domination from an algorithmic point of view. A 2-stratified (or black-white) graph is a graph in which every vertex is colored black or white. Given a black-white graph F rooted at a white vertex v, an F-coloring of a graph G = (V, E) is a black-white coloring of V for which every white vertex v of G belongs to a copy of F (not necessarily induced in G) rooted at v. An F-dominating set of G is the set of all black vertices in an F-coloring. The F-domination number gamma(F)(G) of G is the minimum cardinality of an F-dominating set. We consider the 3-vertex black-white graph F-3 rooted at a white vertex v adjacent to another white vertex u, which adjacent to a black vertex w. We prove that the F-3-domination problem is NP-complete for bipartite planar graphs and for chordal graphs. We also give a linear-time algorithm for the F-3-domination problem in trees. (C) 2013 Elsevier B.V. All rights reserved.
As well known the rotation distance D(S, T) between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation o...
详细信息
As well known the rotation distance D(S, T) between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation on a tree, involving two chains of vertices, that requires changing exactly three pointers in the data structure as for a standard rotation, and define the corresponding chain distance C(S, T). As for D(S, T), no polynomial time algorithm to compute C(S, T) is known. We prove a constructive upper bound and an analytical lower bound on C(S, T) based on the number of maximal chains in the two trees. More precisely we prove the general upper bound C(S, T) <= n - 1 and we show that there are pairs of trees for which this bound is tight. No similar result is known for D(S, T) where the best upper and lower bounds are 2n - 6 and 5/3n - 4 respectively. (C) 2013 Elsevier B.V. All rights reserved.
Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximu...
详细信息
Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of C. The cycle-radius of H is similarly defined except that cycles are replaced by directed closed walks. We prove that there exists for every nonnegative edge weight function an orientation H of G whose cycle-radius equals that of G if and only if G is series-parallel. (C) 2011 Elsevier B.V. All rights reserved.
The constrained LCS (CLCS) problem, a recent variant of the longest common subsequence (LCS) problem, has gained much attention. Given two sequences X and Y of lengths n and m, respectively, and the constrained sequen...
详细信息
The constrained LCS (CLCS) problem, a recent variant of the longest common subsequence (LCS) problem, has gained much attention. Given two sequences X and Y of lengths n and m, respectively, and the constrained sequence P of length r, previous research shows that the CLCS problem can be solved by either an 0(nmr)-time algorithm based upon dynamic programming (DP) techniques or an 0(r R log log(n + m))-time Hunt-Szymanski-like algorithm, where,R is the total r umber of ordered pairs of positions at which the two strings match. In this paper, we investigate the case that X, Y and P are all in run-length encoded (RLE) format, where the numbers of runs are N, M and R, respectively. We first show that when the sequences are encoded, the CLCS problem can be solved by a simple algorithm in 0(nmR + nMr + Nmr) time without decompressing the sequences. Then, we propose a more efficient algorithm with 0(NMr + r x min{q(1), q(2)} + q(3)) time, where q(1) and q(2) denote the numbers of elements in the south and east faces of the matched blocks on the first layer, respectively, and q(3) denotes the number of face elements of all fully matched cuboids in the DP lattice. (C) 2012 Elsevier B.V. All rights reserved.
This paper introduces new problem-size reduction heuristics for the multidimensional knapsack problem. These heuristics are based on solving a relaxed version of the problem, using the dual variables to formulate a La...
详细信息
This paper introduces new problem-size reduction heuristics for the multidimensional knapsack problem. These heuristics are based on solving a relaxed version of the problem, using the dual variables to formulate a Lagrangian relaxation of the original problem, and then solving an estimated core problem to achieve a heuristic solution to the original problem. We demonstrate the performance of these heuristics as compared to legacy heuristics and two other problem reduction heuristics for the multi-dimensional knapsack problem. We discuss problems with existing test problems and discuss the use of an improved test problem generation approach. We use a competitive test to highlight the performance of our heuristics versus the legacy heuristic approaches. We also introduce the concept of computational versus competitive problem test data sets as a means to focus the empirical analysis of heuristic performance. Published by Elsevier Ltd.
Hypergraph width measures are important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. As a consequence, ...
详细信息
Hypergraph width measures are important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. As a consequence, we obtain algorithms which, for a hypergraph H on n vertices and m hyperedges, compute its generalized hypertree-width in time O*(2(n)) and its fractional hypertree-width in time O(1.734601(n) .m)(3). (C) 2011 Elsevier B.V. All rights reserved.
This paper investigates probabilistic single obnoxious facility location with fixed budget which is defined as locating the facility to maximize the probability that the minimum weighted distance from the facility to ...
详细信息
This paper investigates probabilistic single obnoxious facility location with fixed budget which is defined as locating the facility to maximize the probability that the minimum weighted distance from the facility to all non-expropriated demand nodes exceeds a given threshold and the maximum weighted distance from the facility to all expropriated demand nodes does not exceed another given value, where demand weights are random variables with general continuous probability distributions. Properties of the optimal solutions are identified and heuristic solution procedures are presented, especially under the condition of some specific probability distributions. The general problem we propose also leads to some known problems such as maximin, quantile location problems. (C) 2011 Published by Elsevier B.V.
We pose a new visualization challenge, asking Graph Drawing algorithms to cope with the requirements of Streaming applications. In this model a source produces a graph one edge at a time. When an edge is produced, it ...
详细信息
We pose a new visualization challenge, asking Graph Drawing algorithms to cope with the requirements of Streaming applications. In this model a source produces a graph one edge at a time. When an edge is produced, it is immediately drawn and its placement cannot be altered. The drawing has an image persistence, that controls the lifetime of edges. If the persistence is k, an edge remains in the drawing for the time spent by the source to generate k edges, and then it fades away. In this model we study the area requirement of planar straight-line grid drawings of trees and we assess the output quality of the presented algorithms by computing the competitive ratio with respect to the best known offline algorithms. (C) 2012 Elsevier B.V. All rights reserved.
In the problem MIN-DESC, we are given a digraph D and an integer k, and asked whether there exists a set A' of at most k arcs in D, such that if we remove the arcs of A', in the resulting digraph every strong ...
详细信息
In the problem MIN-DESC, we are given a digraph D and an integer k, and asked whether there exists a set A' of at most k arcs in D, such that if we remove the arcs of A', in the resulting digraph every strong component is Eulerian. MIN-DESC is NP-hard;Cechlarova and Schlotter (IPEC 2010) asked whether the problem is fixed-parameter tractable when parameterized by k. We consider the subproblem of MIN-DESC when D is a tournament. We show that this problem is fixed-parameter tractable with respect to k. (C) 2011 Elsevier B.V. All rights reserved.
Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x. V. In the conditional covering problem, a vertex x. V covers a vertex y. V (x is an element o...
详细信息
Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x. V. In the conditional covering problem, a vertex x. V covers a vertex y. V (x is an element of not equal y) if d(x, y) = R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C subset of V so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n(2)) time, when G is an interval graph containing n vertices.
暂无评论