Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by cert...
详细信息
Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial-time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ at most by a factor of two. The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that RELATIVE CLIQUEWIDTH and RELATIVE NLC-WIDTH differ significantly in computational complexity. While the former problem is NP-complete the latter is solvable in polynomial time. The relative NLC-width can be computed in O(n(3)) time, which also yields an exact algorithm for computing the NLC-width in time O(3(n)n). Additionally, our technique enables a combinatorial characterisation of NLC-width that avoids the usual operations on labelled graphs. (c) 2010 Published by Elsevier B.V.
Given a graph G = (V, E), the edge dominating set problem is to find a minimum set M subset of E such that each edge in E - M has at least one common endpoint with an edge in M. The edge dominating set problem is an i...
详细信息
ISBN:
(纸本)9783642174605
Given a graph G = (V, E), the edge dominating set problem is to find a minimum set M subset of E such that each edge in E - M has at least one common endpoint with an edge in M. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721(n)) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306(k))-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an edge dominating set of size k or not. Above two results improve previously known results on exact and parameterized algorithms for this problem.
For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such re...
详细信息
For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this, we use an approach, that we call "Measure& Conquer", as an attempt to step beyond such limitations. The approach is based on the careful design of a nonstandard measure of the subproblem size;this measure is then used to lower bound the progress made by the algorithm at each branching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis. In order to show the potentialities of Measure & Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new, simple algorithm, and show that its running time is competitive with the current best time bounds, achieved with far more complicated algorithms (and standard analysis). Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.
The 2-DISJOINT CONNECTED SUBGRAPHS problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets h...
详细信息
The 2-DISJOINT CONNECTED SUBGRAPHS problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The LONGEST PATH CONTRACTIBILITY problem asks for the largest integer l for which an input graph can be contracted to the path P-l on l vertices. We show that the computational complexity of the LONGEST PATH CONTRACTIBILITY problem restricted to P-l-free graphs jumps from being polynomially solvable to being NP-hard at l = 6, while this jump occurs at l = 5 for the 2-DISJOINT CONNECTED SUBGRAPHS problem. We also present an exact algorithm that solves the 2-DISJOINT CONNECTED SUBGRAPHS problem faster than O*(2(n)) for any n-vertex P-l-free graph. For l = 6, its running time is O*(1.5790(n)). We modify this algorithm to solve the LONGEST PATH CONTRACTIBILITY problem for PG-free graphs in O*(1.5790(n)) time. (C) 2009 Elsevier B.V. All rights reserved.
We do Computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps bo...
详细信息
We do Computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques ("isolated maximal" vs "maximal isolated"). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter "degree of isolation". We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the G(n,m,p) model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks. (C) 2009 Elsevier B.V. All rights reserved.
In an undirected graph G = (V, E), a set of k vertices is called c-isolated if it has less than c . k outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactio...
详细信息
In an undirected graph G = (V, E), a set of k vertices is called c-isolated if it has less than c . k outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on algorithms (2008) (in press)] gave an algorithm to enumerate all c-isolated maximal cliques in O(4(c) . c(4). vertical bar E vertical bar) time. We extend this to enumerating all maximal c-isolated cliques (which are a superset) and improve the running time bound to O(2.89(c). c(2) . vertical bar E vertical bar), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s-plex is the parameter and a fixed-parameter algorithm for enumerating isolated s-plexes when the parameter describes the degree of isolation. (C) 2009 Elsevier B.V. All rights reserved.
In this paper, we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems...
详细信息
In this paper, we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems with non-integer data without necessary transformations of the corresponding problem. We compare the proposed method with existing algorithms for these problems on small-size instances of the partition problem with n <= 10 numbers. For almost all instances, the new algorithm considers on average substantially less "stages" than the dynamic programming algorithm. Crown Copyright (C) 2009 Published by Elsevier Ltd. All rights reserved.
Many applications like image processing,data compression or pattern recognition require a covering of a set of n points most often located in the (discrete) plane by rectangles due to specific cost constraints. In thi...
详细信息
Many applications like image processing,data compression or pattern recognition require a covering of a set of n points most often located in the (discrete) plane by rectangles due to specific cost constraints. In this paper we provide exact dynamic programming algorithms for covering point sets by regular rectangles, that have to obey certain boundary conditions, namely all rectangles must have lengths of at least k, which is a prescribed problem parameter. The concrete objective function underlying our optimization problem is the sum of area, circumference and a constant over all rectangles forming a covering. This objective function can be motivated by requirements of numerically solving PDE's by discretization over (adaptive multi-) grids. More precisely, we propose exact deterministic algorithms for such problems based on a (set theoretic) dynamic programming approach yielding a time bound of O(n(2)3(n)). In a second step this bound is (asymptotically) decreased to O(n(6)2(n)) by exploiting some structural features. Finally, a generalization of the problem and its solution methods is discussed for the case of arbitrary (finite) space dimension.
Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, ...
详细信息
Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3(n) n(O)(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461(n)) time and domatic number in O(2.8718(n)) time. Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and inverted right perpendicular(1 + epsilon)chi(G)inverted left perpendicular in time O(1.2209(n) + 2.2461(e-epsilon n)).
Given an undirected graph G = (V,E) with edge weights and a positive integer number k, the k-cardinality tree problem consists of finding a subtree T of G with exactly k edges and the minimum possible weight. Many alg...
详细信息
Given an undirected graph G = (V,E) with edge weights and a positive integer number k, the k-cardinality tree problem consists of finding a subtree T of G with exactly k edges and the minimum possible weight. Many algorithms have been proposed to solve this NP-hard problem, resulting in mainly heuristic and metaheuristic *** this article, we present an exact ILP-based algorithm using directed cuts. We mathematically compare the strength of our formulation to the previously known ILP formulations of this problem, and show the advantages of our approach. Afterwards, we give an extensive study on the algorithm's practical performance compared to the state-of-the-art *** contrast to the widespread assumption that such a problem cannot be efficiently tackled by exact algorithms for medium and large graphs (between 200 and 5,000 nodes), our results show that our algorithm not only has the advantage of proving the optimality of the computed solution, but also often outperforms the metaheuristic approaches in terms of running time.
暂无评论