This article studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of assigning short labels to the nodes of any n-node graph is such a way that given the labels of a...
详细信息
This article studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of assigning short labels to the nodes of any n-node graph is such a way that given the labels of any two nodes u and v, one can decide whether u and v are k-vertex connected in G, that is, whether there exist k vertex disjoint paths connecting u and v. This article establishes an upper bound of k(2) log n on the number of bits used in a label. The best previous upper bound for the label size of such a labeling scheme is 2(k) log n.
We study ways to expedite Yates's algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point...
详细信息
We study ways to expedite Yates's algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an n-element universe U and a family F of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of U with k sets from F in time within a polynomial factor (in n) of the number of supersets of the members of F. Relying on an projection theorem of Chung et al. (J. Comb. Theory Ser. A 43:23-37, 1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs with maximum degree Delta. In particular, we show how to compute the domatic number in time within a polynomial factor of (2(Delta+1)-2) (n/(Delta+1)) and the chromatic number in time within a polynomial factor of (2(Delta+1)-Delta-1) (n/(Delta+1)). For any constant Delta, these bounds are O((2-epsilon) (n) ) for epsilon > 0 independent of the number of vertices n.
Large resistor networks arise during the design of very-large-scale integration chips as a result of parasitic extraction and electro static discharge analysis. Simulating these large parasitic resistor networks is of...
详细信息
Large resistor networks arise during the design of very-large-scale integration chips as a result of parasitic extraction and electro static discharge analysis. Simulating these large parasitic resistor networks is of vital importance, since it gives an insight into the functional and physical performance of the chip. However, due to the increasing amount of interconnect and metal layers, these networks may contain millions of resistors and nodes, making accurate simulation time consuming or even infeasible. We propose efficient algorithms for three types of analysis of large resistor networks: 1) computation of path resistances;2) computation of resistor currents;and 3) reduction of resistor networks. The algorithms are exact, orders of magnitude faster than conventional approaches, and enable simulation of very large networks.
A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in biology-to compare evolutionary histories of host and parasite species ...
详细信息
A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in biology-to compare evolutionary histories of host and parasite species and to analyze genes of species in the same geographical area. We consider optimization problems in tanglegram drawings. We show a linear time algorithm to decide if a tanglegram admits a planar embedding by a reduction to the planar graph drawing problem. This problem was also studied by Fernau et al. [15]. A similar reduction to a graph crossing problem also helps to solve an open problem they posed, showing a fixed-parameter tractable algorithm for minimizing the number of crossings over all d-ary trees. For the case where one tree is fixed, we show an O(n log n) algorithm to determine the drawing of the second tree that minimizes the number of crossings. This improves the bound from earlier methods. We introduce a new optimization criterion using Spearman's footrule distance and give an O(n(2)) algorithm. We also show integer programming formulations to quickly obtain tanglegram drawings that minimize the two optimization measures discussed. We prove lower bounds on the maximum gap between the optimal solution and the heuristic of Dwyer and Schreiber [13] to minimize crossings.
The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n(5/4) log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n(2)) algorithm for this ...
详细信息
The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n(5/4) log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n(2)) algorithm for this problem. We also extend our results for the class of graphs embedded into an orientable surface of small genus. Our approach uses several techniques such as graph partitioning, hammock decomposition, graph covering, and dynamic shortest-path computation. We discuss extensions and generalizations of our result.
We present an online algorithm for routing the automorphisms (BPC permutations) of the queueless MIMD hypercube. The routing algorithm has the virtue of being executed by each node of the hypercube without knowing the...
详细信息
We present an online algorithm for routing the automorphisms (BPC permutations) of the queueless MIMD hypercube. The routing algorithm has the virtue of being executed by each node of the hypercube without knowing the state of the others nodes. The algorithm is also vertex and link-contention free. We show, using the proposed algorithm, that BPC permutations are arbitrarily routable in the considered communication model. (C) 2010 Elsevier B.V. All rights reserved.
A spanning tree T of a graph G = (V, E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v is an element of V. The problem of recognizing whet...
详细信息
A spanning tree T of a graph G = (V, E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v is an element of V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively. (C) 2010 Elsevier B.V. All rights reserved.
We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multipath connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance ...
详细信息
We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multipath connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance against node failures and high overall network capacity (by the max-flow min-cut theorem). We design and analyze the first algorithms that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any desired parameter. Our algorithms have provable guarantees on the quality of the solution. Specifically, we prove that the number of additional sensors is within a constant factor of the absolute minimum, for any fixed k. We have implemented greedy and distributed versions of this algorithm, and demonstrate in simulation that they produce high-quality placements for the additional sensors.
Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grotzsch's theorem states that every triangle-free planar graph is 3-colorable. We show the fi...
详细信息
Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grotzsch's theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n(2)) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is O(n log n).
We present an O(n) Breadth-First Search algorithm for trapezoid graphs, which takes as input a trapezoid model and any priority order on the vertices. Our algorithm is the first able to produce any BFS-tree, and not o...
详细信息
We present an O(n) Breadth-First Search algorithm for trapezoid graphs, which takes as input a trapezoid model and any priority order on the vertices. Our algorithm is the first able to produce any BFS-tree, and not only one specific to the model given as input, within this complexity. Moreover, it produces all the shortest paths from the root of the BFS-tree to the other vertices of the graph. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论