The Steiner Minimal Tree (SMT) problem is a very important problem in very large scale integrated computer-aided design. Given n points on a plane, an SMT connects these points through some extra points (called Steine...
详细信息
The Steiner Minimal Tree (SMT) problem is a very important problem in very large scale integrated computer-aided design. Given n points on a plane, an SMT connects these points through some extra points (called Steiner points) to achieve a minimal total length. Even though there exist many heuristic algorithms for this problem, they have either poor performances or expensive running time. This paper records an implementation of an efficient SMT algorithm that has a worst case running time of 0 (n log n) and a performance close to that of the Iterated 1-Steiner algorithm. The algorithm efficiently combines Borah et al.'s edge substitute concept with Zhou et aL's spanning graph. Extensive experimental studies are conducted to compare it with other programs.
We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n(3)(log log n/log n)(5/7)) time. This improves the best previous result which runs in O(n(3)(log log n/...
详细信息
We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n(3)(log log n/log n)(5/7)) time. This improves the best previous result which runs in O(n(3)(log log n/log n)(1/2)) time. (C) 2004 Elsevier B.V. All rights reserved.
In this paper, we study the complexity of recognizing powers of chordal graphs and its subclasses. We present the first polynomial time algorithm to recognize squares of proper interval graphs and give an outline of a...
详细信息
In this paper, we study the complexity of recognizing powers of chordal graphs and its subclasses. We present the first polynomial time algorithm to recognize squares of proper interval graphs and give an outline of an algorithm to recognize kth powers of proper interval graphs for every natural number k. These are the first results of this type for a family of graphs that contains arbitrarily large cliques. On the other hand, we show the NP-completeness of recognizing squares of chordal graphs, recognizing squares of split graphs, and recognizing chordal graphs that are squares of some graph.
A system-on-a-chip is an interconnection of different pre-verified IP hardware blocks, which communicate using complex protocols. The integration of IP blocks requires some glue logic to interface otherwise incompatib...
详细信息
A system-on-a-chip is an interconnection of different pre-verified IP hardware blocks, which communicate using complex protocols. The integration of IP blocks requires some glue logic to interface otherwise incompatible datapaths. This glue logic is called a protocol converter and its manual design proves to be a tedious and time-consuming task. Automatic synthesis is therefore important, but for optimal system-level design it is necessary to consider not just the correctness, but also the quality (in terms of bandwidth and latency of data transfer) of the converter. A good solution to this problem will allow greater use of protocol-level abstraction as a design tool in system design and synthesis. Results are presented on automatic synthesis of a converter between two protocols. It is shown how converter logic which is bandwidth-optimal can be synthesised for datapaths with an arbitrary number of data ports each of which has arbitrary-size first-in first-out (FIFO) storage. An extension of the product FSM converter synthesis algorithm to include FIFO data-paths is presented. In addition the converter bandwidth is identified as a mean cycle graph problem which is solved using maximum mean cycle graph algorithms.
Many approaches, to generating a test from an FSM M, are based aroundproducing a test sequence that contains some set T of predefined sequences that, between them, testthe transitions of M. In some cases, in order to ...
详细信息
Many approaches, to generating a test from an FSM M, are based aroundproducing a test sequence that contains some set T of predefined sequences that, between them, testthe transitions of M. In some cases, in order to include each element of T it is necessary to useresets. The use of resets may increase the cost of testing and reduce the effectiveness of *** paper has considered the problem of producing a test sequence that contains the elements of Twhile using as few resets as possible. The paper has introduced an algorithm that represents theoptimization problem in terms of the Rural Chinese Postman Problem (RCPP). Since the RCPP isNP-hard, a heuristic is adapted. The resultant polynomial time algorithm is guaranteed to minimizethe number of resets used, when overlap between the elements of T is not utilized. Sometimes,overlap can be used to further reduce the number of resets. Future work will consider how overlapmay be incorporated.
An (alpha,beta)-spanner of a graph G is a subgraph H such that dist(H)(u,w)less than or equal toalpha. distt(G)(u,w)+beta for every pair of vertices u,w, where dist(G') (u,w) denotes the distance between two verti...
详细信息
An (alpha,beta)-spanner of a graph G is a subgraph H such that dist(H)(u,w)less than or equal toalpha. distt(G)(u,w)+beta for every pair of vertices u,w, where dist(G') (u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2kappa-1,0)-spanner (also known as multiplicative (2kappa-1)-spanner) of size O(n(1+1/kappa)) for every integer kappagreater than or equal to1, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size (O) over tilde (n(3/2)). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant epsilon, lambda>0 there exists a constant beta=beta(epsilon,lambda) such that for every n-vertex graph G there is an efficiently constructible (1 +epsilon,beta)-spanner of size O(n(1+lambda)).
作者：
Thomas, ACannings, CUniv Utah
Dept Med Informat Salt Lake City UT 84112 USA Univ Utah
Ctr High Performance Comp Salt Lake City UT 84112 USA Univ Sheffield
Royal Hallamshire Hosp Div Genom Med Sheffield S10 2JF S Yorkshire England
graph algorithms previously developed by the authors are adapted to simulate pedigrees similar to those used in genetic linkage studies which associate disease phenotypes with specific genomic locations. Pedigrees are...
详细信息
graph algorithms previously developed by the authors are adapted to simulate pedigrees similar to those used in genetic linkage studies which associate disease phenotypes with specific genomic locations. Pedigrees are chosen uniformly at random from the set of those with specified numbers of individuals and matings and which contain no loops. Summary statistics from pedigrees generated in this way can be used to check real pedigrees for anomalies due to biased sampling or phenotypic effects on the pedigree structure.
Let G = (V, E) be a simple, undirected, unweighted, connected graph. A cut (A, (A) over bar) defined by a subset A of V is called trivial if either A or (A) over bar is a singleton set. Let mu be the second smallest e...
详细信息
Let G = (V, E) be a simple, undirected, unweighted, connected graph. A cut (A, (A) over bar) defined by a subset A of V is called trivial if either A or (A) over bar is a singleton set. Let mu be the second smallest eigenvalue of the Laplacian matrix of G. The length of the shortest cycle in the graph is called the girth g of the graph. Let the minimum degree of the graph be delta greater than or equal to 3. We show that if mu is greater than a threshold, namely 8delta/((delta - 1)([(g - 1)/2]) - 2), then every minimum cut in G is trivial. The proof is based on the observation that in graphs of large girth and minimum degree delta greater than or equal to 3, there exists a dichotomy of minimum cuts: Either the minimum cut is trivial or there must be a lot of vertices (Omega((delta - 1)([(g - 1)/2]))) on both sides of the cut. We illustrate that, for large enough values of g, the value obtained by us for this threshold is of the correct order by constructing a graph with girth at least g and minimum degree delta and mu = Omega(g(-1)(delta - 1)(-[(g - 1)/2])), but possessing a nontrivial minimum cut, assuming that a well-known conjecture about the existence of certain high girth graphs is true. Our results in this paper have the obvious algorithmic implication that when we have the a priori information that the value of mu for the given graph is greater than the threshold suggested by our theorems, the algorithmic problems of finding a minimum cut or enumerating all the minimum cuts in the graph becomes trivial. (C) 2003 Elsevier B.V All rights reserved.
The design of efficient graph algorithms usually precludes the test of edge existence, because an efficient support of that operation already requires time Omega(n(2)) for the initialization of an adjacency-matrix rep...
详细信息
The design of efficient graph algorithms usually precludes the test of edge existence, because an efficient support of that operation already requires time Omega(n(2)) for the initialization of an adjacency-matrix representation. We describe an alternative representation of static directed graphs taking Theta(n + m) initialization time and using Theta(n(2)) space, which supports the efficient implementation of all usual operations on static graphs. The sparse graph representation allows the design of efficient graph algorithms using both iteration over all vertices adjacent with a given vertex and edge-existence operations, although at the expense of additional (uninitialized) space which may, nevertheless, be used for other purposes. To the best of our knowledge, the representation leads to the first graph algorithms with the disconcerting property that the time complexity is better than the space complexity. (C) 2004 Elsevier B.V. All rights reserved.
algorithms are presented for external matrix multiplication and for all-pairs shortest path computation. In comparison with earlier algorithms, the amount of I/O is reduced by a constant factor. The all-pairs shortest...
详细信息
algorithms are presented for external matrix multiplication and for all-pairs shortest path computation. In comparison with earlier algorithms, the amount of I/O is reduced by a constant factor. The all-pairs shortest path algorithm even performs fewer internal operations, making the algorithm practically interesting. (C) 2004 Elsevier B.V. All rights reserved.
暂无评论