Given a graph with labels defined on edges and a source-sink pair (s, t), the Label s-t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t. Similarly, ...
详细信息
Given a graph with labels defined on edges and a source-sink pair (s, t), the Label s-t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t. Similarly, the Global Label Cut problem asks for a minimum number of labels to disconnect G itself. For these two problems, we identify two useful parameters, i.e., l(max), the maximum length of any s-t path (only applies to Label s-t Cut), and f(max), the maximum number of appearances of any label in the graph (applies to the two problems). We show that l(max) = 2 and f(max) = 2 are two complexity thresholds for Label s-t Cut Furthermore, we give (i) an O*(c(k)) time parameterized algorithm for Label s-t Cut With (l(max) bounded from above, where parameter k is the number of labels in a solution, and c is a constant with l(max) - 1 < c < l(max), (ii) a combinatorial l(max)-approximation algorithm for Label s-t Cut, and (iii) a polynomial time exact algorithm for Global Label Cut with f(max) bounded from above.. (C) 2016 Elsevier B.V. All rights reserved.
Given a matroid M = (E, I), and a family S of p-subsets of E, a subfamily (S) over cap subset of S represents S if for any X is an element of S and Y subset of E \ X satisfying X boolean OR Y is an element of I, there...
详细信息
Given a matroid M = (E, I), and a family S of p-subsets of E, a subfamily (S) over cap subset of S represents S if for any X is an element of S and Y subset of E \ X satisfying X boolean OR Y is an element of I, there is a set (X) over cap is an element of (S) over cap disjoint from Y, where (X) over cap boolean OR Y is an element of I. We show that a powerful technique for computing representative families, introduced by Fomin et al, (2014)15], leads to a unified approach for substantially improving the running times of parameterized algorithms for some classic problems. This includes k-PARTIAL COVER, k-INTERNAL OUT-BRANCHING, and LONG DIRECTED CYCLE, among others. Our approach exploits an interesting tradeoff between running time and the representative family size. (C) 2015 Elsevier Inc. All rights reserved.
We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function a...
详细信息
We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge e a natural number flex(e), its flexibility. The problem FLEXDRAW asks whether there exists an orthogonal drawing such that each edge e has at most flex(e) bends. It is known that FLEXDRAW is NP-hard if flex(e) = 0 for every edge e [1]. On the other hand, FLEXDRAW can be solved efficiently if flex(e) >= 1 [2] and is trivial if flex(e) >= 2 [3] for every edge e. To close the gap between the NP-hardness for flex(e) = 0 and the efficient algorithm for flex(e) >= 1, we investigate the computational complexity of FLEXDRAW in case only few edges are inflexible (i.e., have flexibility 0). We show that for any epsilon > 0 FLEXDRAW is NP-complete for instances with O (n(epsilon)) inflexible edges with pairwise distance Omega(n(1-epsilon)) (including the case where they induce a matching), where n denotes the number of vertices in the graph. On the other hand, we give an EFT-algorithm with running time O (2(k) . n . T-flow(n)), where T-flow(n) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and k is the number of inflexible edges having at least one endpoint of degree 4. (C) 2016 Elsevier B.V. All rights reserved.
We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O*(rho(k)), where rho = root root 2 + 1 <...
详细信息
We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O*(rho(k)), where rho = root root 2 + 1 < 1.554 is the positive root of the polynomial x(4) - 2x(2) - 1. This improves the current-best algorithm of Chen et al. that runs in time O*(1.619(k)). For the GENERALIZED MULTIWAY CUT ON TREES problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed;this answers an open question posed in a recent paper by Liu and Zhang. By reducing the GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZED MULTIWAY CUT ON TREES problem in time O*(rho(k)). (C) 2015 Elsevier B.V. All rights reserved.
The parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R-d (d-RSP), for a given set S of n points in R-d and a positive integer k, is to find a rectilinear spannin...
详细信息
The parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R-d (d-RSP), for a given set S of n points in R-d and a positive integer k, is to find a rectilinear spanning path P with at most k line-segments that cover all points in S, where all line-segments in P are axis-parallel. In this paper, we study a constrained d-RSP problem (Constrained d-RSP problem) in which each line-segment l in the spanning path must cover all the points in S that share the same line with l. By applying the branch-and-search and dynamic programming techniques, a parameterized algorithm with running time 0*((1 + root 1 + 4(d - 1)(2))(k)) is given for the Constrained d-RSP problem, which significantly improves the current best result 0*((0.74dk)(k)). (C) 2014 Elsevier B.V. All rights reserved.
We consider the problem of covering a given set of points in the Euclidean space R-m by a small number k of hyperplanes of dimensions bounded by d, where d <= m. We present a very simple parameterized algorithm for...
详细信息
We consider the problem of covering a given set of points in the Euclidean space R-m by a small number k of hyperplanes of dimensions bounded by d, where d <= m. We present a very simple parameterized algorithm for the problem, and give thorough mathematical analysis to prove the correctness and derive the complexity of the algorithm. When the algorithm is applied on the standard HYPERPLANE-COVER problem in R-d, it runs in time O*(k((d-1)k)/1.3(k)) improving the previous best algorithm of running time O*(k(dk+d)) for the problem. When the algorithm is applied on the LINE-COVER problem in R-2, it runs in time O*(k(k)/1.35(k)) improving the previous best algorithm of running time O*(k(2)k/4.84(k)) for the problem. (C) 2010 Elsevier B.V. All rights reserved.
Let G = (V, E) be a graph of order n and let B(D) be the set of vertices in V\D that have a neighbor in the vertex set D. The differential of D is defined as partial derivative(D) = vertical bar B(D)vertical bar - ver...
详细信息
Let G = (V, E) be a graph of order n and let B(D) be the set of vertices in V\D that have a neighbor in the vertex set D. The differential of D is defined as partial derivative(D) = vertical bar B(D)vertical bar - vertical bar D vertical bar and the differential of a graph G, written partial derivative(G), is equal to max{partial derivative(D) : D subset of V}. If G is connected and n >= 3, partial derivative(G) >= n/5 is known. This immediately leads to a linear vertex kernel result (in the terminology of parameterized complexity) for the problem of deciding whether partial derivative(G) >= k, taking k as the parameter. We then establish a new combinatorial result which establishes that partial derivative(G) >= n/4 if G is a connected graph of order n >= 6 and if G contains no induced path of five vertices whose midpoint is a cut vertex and whose endpoints have degree one. This technical combinatorial theorem can be used to derive an even smaller linear vertex kernel for general graphs. Also, we show that the related maximization problem allows for a polynomial-time factor-1/4 approximation algorithm. (C) 2014 Elsevier B.V. All rights reserved.
We study the calculation of the largest pairwise intersections in a given set family. We give combinatorial and algorithmic results both for the worst case and for set families where the frequencies of elements follow...
详细信息
We study the calculation of the largest pairwise intersections in a given set family. We give combinatorial and algorithmic results both for the worst case and for set families where the frequencies of elements follow a power law, as words in texts typically do. The results can be used in faster preprocessing routines in a simple approach to multi-document summarization. (C) 2015 Elsevier B.V. All rights reserved.
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, whe...
详细信息
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, where p is a constant between 0 and 1. We show that a maximum independent set in a random graph that contains n vertices can be computed in expected computation time 2(O(log22 n)). In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in n vertices can be approximated within a ratio of 2n/2(root log2 n) in expected polynomial time.
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor *** core of these programs are algorithms to solve kidney exchange problem, which can...
详细信息
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor *** core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed *** generally, the objective function is maximizing the number of possible kidney *** this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle ***, we formal the kidney exchange problem as a parameterized *** then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the ***, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2[log k2/2.k3[logk3]/2.42k3.22k2) is given for the parameterized kidney ***,our randomized algorithms can be extended to solve the general kidney exchange problem.
暂无评论