1,720,964 research outputs found
Exact Exponential-Time Algorithms for Domination Problems in Graphs
No full textThis PhD thesis studies exact exponential-time algorithms for domination problems in graphs. Domination problems in graphs are a special kind of subset problems in graphs. A subset problem in a graph is a problem where one is given a graph G=(V,E), and one is asked whether there exist some subset S of a set of items U in the graph (mostly U is either the vertices V or the edges E) that satisfies certain properties. Domination problems in graphs are subset problems in which there is a domination criterion based on a neighbourhood relation in the graph that decides which elements of U are dominated by a given subset S, and where one of the properties that a solution subset S must satisfy is that S must dominate its complement U\S. The most well-known graph domination problem is the Dominating Set problem where the set U is the set of vertices V of G, a vertex subset S dominates all vertices in G that have a neighbour in S, and one is asked to compute the smallest vertex subset S of V that dominates all vertices in V\S. Other examples of domination problems in graphs are Independent Set, Edge Dominating Set, Total Dominating Set, Red-Blue Dominating Set, Partial Dominating Set, and #Dominating Set. We study exact exponential-time algorithms for these problems. These are algorithms that, when executed, use a number of operations that is exponential in a complexity parameter of the input in the worst case. That is, these algorithms use exponential time. Exact exponential-time algorithms then return an optimal solution to the problem. This in contrast to other fields of algorithm design where one sometimes trades running time for other properties of the algorithm or the returned solution. In this thesis, we also study parameterised algorithms for domination problems in graph on graph decompositions. These are algorithms whose worst-case running times are polynomial in the size of the graph and exponential in the graph-width parameter associated to the graph decomposition. Our study led to faster exact exponential-time algorithms for many well-known graph domination problems. This includes an O(1.4969^n)-time algorithm for Dominating Set, an O(1.2114^n)-time algorithm for Independent Set, an O(1.3226^n)-time algorithm for Edge Dominating Set, an O(1.4969^n)-time algorithm for Total Dominating Set, an O(1.2252^n)-time algorithm for Red-Blue Dominating Set, an O(1.5014^n)-time algorithm for Partial Dominating Set, and an O(1.5002^n)-time algorithm for #Dominating Set. We also obtained faster algorithms for these and many other graph domination problems on some prominent types of graph decompositions: tree decompositions, branch decompositions, and, for some problems, clique decompositions (also called k-expressions). A series of interesting new insights and techniques arose from this study. We mention the techniques of inclusion/exclusion-based branching and extended inclusion/exclusion-based branching. We also mention our generalisation of the fast subset convolution algorithm, which we translated to the setting of state-based dynamic programming algorithms on graph decompositions. This thesis also contains an accessible introduction to the field of exact exponential-time algorithms
Treewidth Computations II. Lower Bounds
No full textAbstractFor several applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs
Complexity Results for the Spanning Tree Congestion Problem
Full text linkWe study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the complexity of this problem. First, we show that for every fixed k and d the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k ≥ 10. For very small values of k however, the problem becomes polynomially solvable. We also show that it is NP-hard to approximate the spanning tree congestion within a factor better than 11/10. On planar graphs, we prove the problem is NP-hard in general, but solvable in linear time for fixed k
Path Planning for Groups using Column Generation
No full textIn computer games, one or more groups of units need to move from one location to another as quickly as possible. If there is only one group, then it can be solved efficiently as a dynamic flow problem. If there are several groups with different origins and destinations, then the problem becomes -hard. In current games, these problems are solved by using greedy ad hoc rules, leading to long traversal times or congestions and deadlocks near narrow passages. We present a centralized optimization approach based on Integer Linear Programming. Our solution provides an efficient heuristic to minimize the average and latest arrival time of the units
Characterizing width two for variants of treewidth
Full text linkIn this paper, we consider the notion of special treewidth , recently introduced by Courcelle (2012). In a special tree decomposition, for each vertex vv in a given graph, the bags containing vv form a rooted path. We show that the class of graphs of special treewidth at most two is closed under taking minors, and give the complete list of the six minor obstructions. As an intermediate result, we prove that every connected graph of special treewidth at most two can be constructed by arranging blocks of special treewidth at most two in a specific tree-like fashion.
Inspired by the notion of special treewidth, we introduce three natural variants of treewidth, namely spaghetti treewidth, strongly chordal treewidth and directed spaghetti treewidth. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a tree of cycles with additional conditions. Finally, we show that for each k=3k=3, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most kk, is not closed under taking minors.
Keywords: Treewidth; Special treewidth; Spaghetti treewidth; Strongly chordal treewidth; Mino
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
No full textIt is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2O(tw)nO(1) time for graphs with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time it was unknown how to do this faster than twO(tw)nO(1) until recently, when Cygan et al. (FOCS 2011) introduced the Cut&Count technique that gives randomized algorithms for a wide range of connectivity problems running in time ctwnO(1) for a small constant c. In this paper, we show that we can improve upon the Cut&Count technique in multiple ways, with two new techniques. The first technique (rank-based approach) gives deterministic algorithms with O(c tw n) running time for connectivity problems (like Hamiltonian Cycle and Stei-ner Tree) and for weighted variants of these; the second technique (determinant approach) gives deterministic algorithms running in time ctwnO(1) for counting versions, e.g., counting the number of Hamiltonian cycles for graphs of treewidth tw. The rank-based approach introduces a new technique to speed up dynamic programming algorithms which is likely to have more applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming
Routing for analog chip designs at NXP Semiconductors
No full textDuring the study week 2011 we worked on the question of how to automate certain aspects of the design of analog chips. Here we focused on the task of connecting different blocks with electrical wiring, which is particularly tedious to do by hand. For digital chips there is a wealth of research available for this, as in this situation the amount of blocks makes it hopeless to do the design by hand. Hence, we set our task to finding solutions that are based on the previous research, as well as being tailored to the specific setting given by NXP. This resulted in an heuristic approach, which we presented at the end of the week in the form of a protoype tool. In this report we give a detailed account of the ideas we used, and describe possibilities to extend the approach
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
