Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G = (V. E) on n vertices, a pair (X. Y), with X, Y s...
详细信息
Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G = (V. E) on n vertices, a pair (X. Y), with X, Y subset of V, X boolean AND Y = mt set, is a non-induced biclique if {x, y} is an element of E for any x is an element of X and y is an element of Y. The NP-complete problem of finding a non-induced (k(1), k(2))-biclique asks to decide whether G contains a non-induced biclique (X. Y) such that vertical bar X vertical bar = k(1) and vertical bar Y vertical bar = k(2). In this paper, we design a polynomial-space O(1.6914(n))-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(1.30052(n)). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(1.30052(n)). (C) 2010 Elsevier B.V. All rights reserved.
Graph Coloring Problem, as one of the best known NP-complete problems, has been extensively studied by researchers in a wide range of fields, leading to many applications and theories in mathematics and computer scien...
详细信息
Graph Coloring Problem, as one of the best known NP-complete problems, has been extensively studied by researchers in a wide range of fields, leading to many applications and theories in mathematics and computer science. In this paper, we focus on the design of exactalgorithms for counting 3-colorings of a graph (denoted by #3-COLORING). Our approach is based on branch and reduce paradigm. We use the measure and conquer method to analyze the algorithms, in which we design two sets of measures (weights of vertices) intended for two distinct situations. In particular, we use the tree-width based technique to handle a special case by leveraging dynamic programming. As a result, we obtain an O(1.588n)-time algorithm for the #3-COLORING problem, which improves the previous O(1.6262n)-time algorithm by Fomin et al. (2007). (C) 2022 Elsevier B.V. All rights reserved.
We consider the -hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for gene...
详细信息
We consider the -hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form with ca parts per thousand currency sign2. For graphs with bounded degree, c < 2. The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of when analyzed with respect to the number of vertices. We also show that its running time is when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analysis for parameterized algorithms.
Given a directed graph G = (V, A), the Directed Maximum Leaf Spanning Tree problem asks to compute a directed spanning tree with as many leaves as possible. By designing a branching algorithm analyzed with Measure&...
详细信息
Given a directed graph G = (V, A), the Directed Maximum Leaf Spanning Tree problem asks to compute a directed spanning tree with as many leaves as possible. By designing a branching algorithm analyzed with Measure&Conquer, we show that the problem can be solved in time O*(1.9044(n)) using polynomial space. Allowing exponential space, this run time upper bound can be lowered to O*(1.8139(n)). We also provide an example showing a lower-bound for the running time of our algorithm. (C) 2012 Elsevier B.V. All rights reserved.
The Capacitated Dominating Set problem is the problem of finding a dominating set of minimum cardinality where each vertex has been assigned a bound on the number of vertices it has capacity to dominate. Cygan et al. ...
详细信息
The Capacitated Dominating Set problem is the problem of finding a dominating set of minimum cardinality where each vertex has been assigned a bound on the number of vertices it has capacity to dominate. Cygan et al. showed in 2009 that this problem can be solved in O (n(3)m ( n n/3)) or in O*(1.89(n)) time using maximum matching algorithm. An alternative way to solve this problem is to use dynamic programming over subsets. By exploiting structural properties of instances that cannot be solved fast by the maximum matching approach, and "hiding" additional cost related to considering subsets of large cardinality in the dynamic programming, an improved algorithm is obtained. We show that the Capacitated Dominating Set problem can be solved in O*(1.84630(n)) time. (c) 2012 Elsevier B.V. All rights reserved.
In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules,...
详细信息
In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is NP-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless P = NP. We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains NP-complete (and its optimisation version is APX-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i. e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields W[1]-hardness. Furthermore, we present an O(3(vertical bar w vertical bar)) exactexponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i. e., grammars for which only the start rule contains nonterminals on the right side;thus, investigating the impact of the "hierarchical depth" of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly strong
We study the capacitated vertex cover problem (CVC). In this natural extension to the vertex cover problem, each vertex has a predefined capacity which indicates the total amount of edges that it can cover. In this pa...
详细信息
ISBN:
(纸本)9783030108014;9783030108007
We study the capacitated vertex cover problem (CVC). In this natural extension to the vertex cover problem, each vertex has a predefined capacity which indicates the total amount of edges that it can cover. In this paper, we study the complexity of the CVC problem. We give NP-completeness proofs for the problem on modular graphs, treeconvex graphs, and planar bipartite graphs of maximum degree three. For the first two graph classes, we prove that no subexponential-time algorithm exist for CVC unless the ETH fails. Furthermore, we introduce a series of exact exponential-time algorithms which solve the CVC problem on several graph classes in O((2 - epsilon)(n)) time, for some epsilon > 0. Amongst these graph classes are, graphs of maximum degree three, other degree-bounded graphs, regular graphs, graphs with large matchings, c-sparse graphs, and c-dense graphs. To obtain these results, we introduce an FPT treewidth algorithm which runs in O* ((k + 1)(tw)) or O* (k(k)) time, where k is the solution size and tw the treewidth, improving an earlier algorithm from Dom et al.
暂无评论