We present an efficient algorithm that decides the consistency of partial descriptions of ordered trees. The constraint language of these descriptions was introduced by Cornell in computational linguistics;the constra...
详细信息
We present an efficient algorithm that decides the consistency of partial descriptions of ordered trees. The constraint language of these descriptions was introduced by Cornell in computational linguistics;the constraints specify for pairs of nodes sets of admissible relative positions in an ordered tree. Cornell asked for an algorithm to find a tree structure satisfying these constraints. This computational problem generalizes the common-supertree problem studied in phylogenetic analysis, and also generalizes the network consistency problem of the so-called left-linear point algebra. We present the first polynomial time algorithm for Cornell's problem, which runs in time O(mn), where in is the number of constraints and n the number of variables in the constraint. (C) 2006 Elsevier B.V. All rights reserved.
Cographs are a well-known class of graphs arising in a wide spectrum of practical applications. In this note, we show that the connected components of a cograph G can be optimally found in O (log log log Delta (G)) ti...
详细信息
Cographs are a well-known class of graphs arising in a wide spectrum of practical applications. In this note, we show that the connected components of a cograph G can be optimally found in O (log log log Delta (G)) time using O ((n+m)/log log log Delta(G)) processors on a common CRCW PRAM, or in O (log Delta (G)) time using O ((n+m)/ log Delta (G)) processors on an EREW PRAM, where Delta(G) is the maximum degree of G, and n and m respectively are the numbers of vertices and edges of G. These are faster than the previously best known result on general graphs. (c) 2006 Elsevier Ltd. All rights reserved.
The achromatic number of a graph G = (V, E) with vertical bar V vertical bar = n vertices is the largest number k with the following property: the vertices of G can be partitioned into k independent subsets {V-i}(1)&l...
详细信息
The achromatic number of a graph G = (V, E) with vertical bar V vertical bar = n vertices is the largest number k with the following property: the vertices of G can be partitioned into k independent subsets {V-i}(1)<= i <= k such that for every distinct pair of subsets V-i, V-j in the partition, there is at least one edge in E that connects these subsets. We describe a greedy algorithm that computes the achromatic number of a bipartite graph within a factor of O(n(4/5)) of the optimal. Prior to our work, the best known approximation factor for this problem was n log log n/log n as shown by Kortsarz and Krauthgamer [SIAM J. Discrete Math., 14 (2001), pp. 408-422].
graph data in modern scientific and engineering applications are often too large to fit in the computer's main memory. Input/output (I/O) complexity is a major research issue in this context. Minimization of the n...
详细信息
graph data in modern scientific and engineering applications are often too large to fit in the computer's main memory. Input/output (I/O) complexity is a major research issue in this context. Minimization of the number of I/O operations (in external memory graph algorithms) is the main focus of current research while classical (internal memory) graph algorithms were designed to minimize temporal complexity. In this paper, we propose an external memory depth first search algorithm for general grid graphs. The I/O-complexity of the algorithm is O(sort(N) log(2) N/M), where N = vertical bar V vertical bar + vertical bar E vertical bar, sort(N) = theta(N/M log(M/B) N/B) is the sorting I/O-complexity, M is the memory size, and B is the block size. The best known algorithm for this class of graph is the standard (internal memory) DFS algorithm with appropriate block (sub-grid) I/O-access. Its I/O-complexity is O(N/root B). Recently, the authors proposed an O(sort(N)) algorithm for solid grid graphs. (c) 2007 Elsevier B.V. All rights reserved.
A subset of vertices D subset of V of a graph G = (V, E) is a dominating clique if D is a dominating set and a clique of G. The existence problem 'Given a graph G, is there a dominating clique in G?' is NP-com...
详细信息
A subset of vertices D subset of V of a graph G = (V, E) is a dominating clique if D is a dominating set and a clique of G. The existence problem 'Given a graph G, is there a dominating clique in G?' is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problems are NP-hard. We present an O(1.3387(n)) time and polynomial space algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. The algorithm uses the Branch & Reduce paradigm and its time analysis is based on the Measure & Conquer approach. We also establish a lower bound of Omega(1.2599(n)) for the worst case running time of the algorithm. Finally using memorization we obtain an O(1.3234(n)) time and exponential space algorithm for the same problem. (c) 2007 Elsevier B.V. All rights reserved.
Culberson and Rudnicki [J.C. Culberson, P. Rudnicki, A fast algorithm for constructing trees from distance matrices, Inform. Process. Lett. 30 (4) (1989) 215-220] gave an algorithm that reconstructs a degree d restric...
详细信息
Culberson and Rudnicki [J.C. Culberson, P. Rudnicki, A fast algorithm for constructing trees from distance matrices, Inform. Process. Lett. 30 (4) (1989) 215-220] gave an algorithm that reconstructs a degree d restricted tree from its distance matrix. According to their analysis, it runs in time O(dn log(d) n) for topological trees. However, this turns out to be false;we show that the algorithm takes Theta(n(3/2) root d) time in the topological case, giving tight examples. (c) 2006 Elsevier B.V. All rights reserved.
Alon et. al. [ N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 ( 2000), pp. 451 - 476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is e...
详细信息
Alon et. al. [ N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 ( 2000), pp. 451 - 476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is epsilon- testable. However, the complexity of the test is double- tower with respect to 1/epsilon, as the only tool known to construct such tests uses a variant of Szemeredi's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is epsilon- testable, with a number of queries that is polynomial in 1/ epsilon. Our main tool is a new " conditional" version of the regularity lemma for binary matrices, which may be interesting on its own.
The class of bipartite permutation graphs is the intersection of two well known graph classes: bipartite graphs and permutation graphs. A complete bipartite decomposition of a bipartite permutation graph is proposed i...
详细信息
The class of bipartite permutation graphs is the intersection of two well known graph classes: bipartite graphs and permutation graphs. A complete bipartite decomposition of a bipartite permutation graph is proposed in this note. The decomposition gives a linear structure of bipartite permutation graphs, and it can be obtained in O(n) time, where n is the number of vertices. As an application of the decomposition, we show an O(n) time and space algorithm for finding a longest path in a bipartite permutation graph. (C) 2007 Elsevier B.V. All rights reserved.
Causal modeling and the accompanying learning algorithms provide useful extensions for in-depth statistical investigation and automation of performance modeling. We enlarged the scope of existing causal structure lear...
详细信息
Causal modeling and the accompanying learning algorithms provide useful extensions for in-depth statistical investigation and automation of performance modeling. We enlarged the scope of existing causal structure learning algorithms by using the form-free information-theoretic concept of mutual information and by introducing the complexity criterion for selecting direct relations among equivalent relations. The underlying probability distribution of experimental data is estimated by kernel density estimation. We then reported on the benefits of a dependency analysis and the decompositional capacities of causal models. Useful qualitative models, providing insight into the role of every performance factor, were inferred from experimental data. This paper reports on the results for a LU decomposition algorithm and on the study of the parameter sensitivity of the Kakadu implementation of the JPEG-2000 standard. Next, the analysis was used to search for generic performance characteristics of the applications.
The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695(n) (up to polynomial factors) ...
详细信息
The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695(n) (up to polynomial factors) and in polynomial space. This result improves the previous bound of 2.8805(n), which is due to Bjorklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta (G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta (G) >= 5. Our new randomized algorithm employs Schoning's approach to constraint satisfaction problems. (c) 2006 Elsevier B.V. All rights reserved.
暂无评论