This paper characterizes a class G of partial 4-trees in terms of a set of seven forbidden miners. The class G contains several known classes of graphs, including both Delta - Y and Y - Delta graphs. A set of six grap...
详细信息
This paper characterizes a class G of partial 4-trees in terms of a set of seven forbidden miners. The class G contains several known classes of graphs, including both Delta - Y and Y - Delta graphs. A set of six graph reduction operations is defined, and it is shown that a graph G is an element of G iff G can be reduced to an edgeless graph by a finite sequence of these operations. The all-terminal reliability R(G) of a graph G is the probability that G is connected. The characterization of G is used to develop an O(n log n) algorithm to compute R(G) for all n-point graphs in G. The running time is O(n) for planar graphs in G. (C) 1995 John Wiley and Sons, Inc.
Let P be a property of undirected graphs. We consider the following problem: given a graph G that has property P, find a minimal spanning subgraph of G with property P. We describe general algorithms for this problem ...
详细信息
Let P be a property of undirected graphs. We consider the following problem: given a graph G that has property P, find a minimal spanning subgraph of G with property P. We describe general algorithms for this problem and prove their correctness under fairly weak assumptions about P. We establish that the worst-case running time of these algorithms is Theta(m + n log n) for 2-edge-connectivity and biconnectivity where II and m denote the number of vertices and edges, respectively, in the input graph. By refining the basic algorithms we obtain the first lineartimealgorithms for computing a minimal 2-edge-connected spanning subgraph and for computing a minimal biconnected spanning subgraph. We also devise general algorithms for computing a minimal spanning subgraph in directed graphs. These algorithms allow us to simplify an earlier algorithm of Gibbons, Karp, Ramachandran, Soroker, and Tarjan for computing a minimal strongly connected spanning subgraph. We also provide the first tight analysis of the latter algorithm, showing that its worst-case time complexity is Theta(m + n log n).
The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are us...
详细信息
The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are used. Both the preemptive and the nonpreemptive cases of the problem are considered.
This paper introduces a special class of mathematical programming problem which maximizes the minimal value of a set of linear functions subject to a single linear constraint and upper bounding constraint on each vari...
详细信息
This paper introduces a special class of mathematical programming problem which maximizes the minimal value of a set of linear functions subject to a single linear constraint and upper bounding constraint on each variable. An O(n) algorithm for solving this problem is described by exploiting its special structure.
Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overl...
详细信息
Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting common superstring algorithm runs in timeO(n) or in timeO(n min(logm, log|Σ|)) depending on whether or not the goto transitions of the Aho-Corasick automaton can be implemented by direct indexing over the alphabet Σ. Heren is the total length of the strings inR andm is the number of such strings. The best previously known method requires timeO(n logm) orO(n logn) depending on the availability of direct indexing.
Much of the recent work on the automated design of VLSI chips has concentrated on routing problems associated with such designs. One major class of routing problems focuses on single-row routing. Recently, the traditi...
详细信息
Much of the recent work on the automated design of VLSI chips has concentrated on routing problems associated with such designs. One major class of routing problems focuses on single-row routing. Recently, the traditional single-row routing model has been generalized to allow external wires. Under this generalized model, it is possible to route many more single-row routing instances than in the traditional model. There is, however, a clear disadvantage in the use of external wires. since they force a lengthening of the channels surrounding the single row of terminals. Thus, it is desirable for these generalized single-row routings to use a minimum number of external wires. In this note, we provide a linear-time algorithm for determining the minimum number of external wires needed to route a given instance of single-row routing.
The Popular class of series-parallel graphs can be built recursively from single edges by combining smaller components via connections only at a fixed pair of vertices called terminals. This recursive construction pro...
详细信息
The Popular class of series-parallel graphs can be built recursively from single edges by combining smaller components via connections only at a fixed pair of vertices called terminals. This recursive construction property with a limited number of terminals is essential to the lineartime solution of problems on these graphs. A second useful property of these graphs is that decomposition is deterministic with respect to the series-parallel rules. This implies that the parse-tree of decomposition (which is required by the algorithms) can be determined in a straightforward manner by repeatedly applying the decomposition rules. Subject to retaining these properties, we examine how far the series-parallel graphs can be generalized. Corollaries of our results yield the deterministic decomposition of the series-parallel and Halin graph classes.
In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are descri...
详细信息
In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or notP is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygonP from whichP is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains inP with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in lineartime.
The class of rectilinear graphs, respectively embedded rectilinear graphs, was introduced by Budach (1978) and examined in the context of maze solving problems. These classes of graphs were independently redefined by...
详细信息
The class of rectilinear graphs, respectively embedded rectilinear graphs, was introduced by Budach (1978) and examined in the context of maze solving problems. These classes of graphs were independently redefined by Vijayan and Wigderson (1985), who were motivated by very large-scale integration (VLSI) layout design problems. They proved a lineartimealgorithm to check the embeddability of rectilinear graphs and an O (n squared) timealgorithm to generate an embedding of any given rectilinear graph on n nodes. A linear-time algorithm is developed to recognize and embed graphs that are embeddable on the plane using a different and surprisingly simple layout strategy. The strategy uses convex faces. The algorithm is well-suited for implementation because of the reasonable constant behind its O(n) time behavior.
A new polygon class taking linear-time and space for triangulation, called an if-polygon, is defined. After describing an algorithm for triangulating this class, we show that some triangulation-linear classes previous...
详细信息
A new polygon class taking linear-time and space for triangulation, called an if-polygon, is defined. After describing an algorithm for triangulating this class, we show that some triangulation-linear classes previously known, such as a convex polygon, a spiral polygon, an edge-visible polygon and a chain-visible polygon have the same property, called the if-property, as the newly defined class. Consequently, a monotone-separable polygon and a star-shaped polygon can be considered as a union of two if-polygons, respectively. Also, we present a modified algorithm for triangulating a star-shaped polygon without decomposition. As a result, the algorithm is simpler to implement and easier to understand and its correctness can be easily verified.
暂无评论