In this study, we consider the problem of estimating the diameter of a graph, that is, the maximum distance between any two vertices, in lineartime. We address a question posed in the literature-whether there exists ...
详细信息
In this study, we consider the problem of estimating the diameter of a graph, that is, the maximum distance between any two vertices, in lineartime. We address a question posed in the literature-whether there exists an interesting graph class with arbitrarily large cycles for which breadth first search (BFS) would always return high-eccentricity vertices. We answer this question positively, defining a class of graphs that generalizes AT-free graphs and has no bound on the size of induced cycles, yet BFS always returns a vertex whose eccentricity is within a constant difference from the diameter. In addition, we consider the question-also explicitly stated in the literature-whether some variant of the so-called multisweep algorithm would always return a high-eccentricity vertex. We show that the answer is negative by describing a family of graphs for which no variant of multisweep BFS can return a vertex of eccentricity higher than half of the diameter plus a constant.
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.
Suffix trees are the fundamental data structure of combinatorial pattern matching on words. Suffix trees have been used in order to give optimal solutions to a great variety of problems oil static words, but for pract...
详细信息
Suffix trees are the fundamental data structure of combinatorial pattern matching on words. Suffix trees have been used in order to give optimal solutions to a great variety of problems oil static words, but for practical situations, such as in a text editor, where the incremental changes of the text make dynamic updating of the corresponding suffix trees necessary, this data structure alone has not been used with success. We prove that, for dynamic modifications of order 0 (1) of words of length it, any suffix tree updating algorithm. such as the ones proposed by McCreight, requires 0(n) worst-case running time, as for the full reconstruction of the suffix tree. Consequently, we argue that this data Structure alone is not appropriate for the solution of combinatorial problems on words that change dynamically.
Updating an abstract Voronoi diagram in lineartime, after deletion of one site, has been an open problem in a long time;similarly, for any concrete Voronoi diagram of generalized (non-point) sites. In this paper we p...
详细信息
Updating an abstract Voronoi diagram in lineartime, after deletion of one site, has been an open problem in a long time;similarly, for any concrete Voronoi diagram of generalized (non-point) sites. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To achieve this result, we use the concept of a Voronoi-like diagram, a relaxed Voronoi structure of independent interest. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under insertion, therefore, enabling its use in incremental constructions. The time-complexity analysis introduces a variant to backwards analysis, which is applicable to order-dependent structures. We further extend the technique to compute in expected lineartime: the order -(k + 1) subdivision within an order -k Voronoi region, and the farthest abstract Voronoi diagram, after the order of its regions at infinity is known.
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.
作者：
Giegerich, RKurtz, STechnische Fakultät
Universität Bielefeld Postfach 100 131 D-33501 Bielefeld Germany. robert@techfak.uni-bielefeld.de kurtz@techfak.uni-bielefeld.de. DE
We review the linear-time suffix tree constructions by Weiner, McCreight, and Ukkonen. We use the terminology of the most recent algorithm, Ukkonen's on-line construction, to explain its historic predecessors. Thi...
详细信息
We review the linear-time suffix tree constructions by Weiner, McCreight, and Ukkonen. We use the terminology of the most recent algorithm, Ukkonen's on-line construction, to explain its historic predecessors. This reveals relationships much closer than one would expect, since the three algorithms are based on rather different intuitive ideas. Moreover, it completely explains the differences between these algorithms in terms of simplicity, efficiency, and implementation complexity.
In this paper, we design an algorithm that, given a directed graph G and the Cartesian-product decomposition of its underlying undirected graph (G) over tilde, produces the directed Cartesian-product decomposition of ...
详细信息
In this paper, we design an algorithm that, given a directed graph G and the Cartesian-product decomposition of its underlying undirected graph (G) over tilde, produces the directed Cartesian-product decomposition of G in lineartime. This is the first time that the linear complexity is achieved for this problem, which has two major consequences. Firstly, it shows that the directed and undirected versions of the Cartesian-product decomposition of graphs are linear-time equivalent problems. And secondly, as there already exists a linear-time algorithm for solving the undirected version of the problem, combined together, it provides the first linear-time algorithm for computing the directed Cartesian-product decomposition of a directed graph. (C) 2015 Elsevier B.V. All rights reserved.
A Steiner tree T on a given set of points A is called linear if all Steiner points. including those collapsing into their adjacent given points, lie on one path referred to as its trunk. Suppose A is a simple polygona...
详细信息
A Steiner tree T on a given set of points A is called linear if all Steiner points. including those collapsing into their adjacent given points, lie on one path referred to as its trunk. Suppose A is a simple polygonal line. Roughly speaking, T is similar to A if its trunk turns light or left when A does. In this paper we prove that A can be expanded to another polygonal line, and T carl be constructed in lineartime using this expansion method.
We prove that every (claw, net)-free graph contains an induced doubly dominating cycle or a dominating pair. Moreover, using LexBFS we present a lineartimealgorithm which, for a given (claw, net)-free graph, finds e...
详细信息
We prove that every (claw, net)-free graph contains an induced doubly dominating cycle or a dominating pair. Moreover, using LexBFS we present a lineartimealgorithm which, for a given (claw, net)-free graph, finds either a dominating pair or an induced doubly dominating cycle. We show also how one can use structural properties of (claw, net)-free graphs to solve efficiently the domination, independent domination, and independent set problems on these graphs. (C) 2003 Elsevier B.V. All rights reserved.
In an ordinary edge-coloring of a graph each color appears at each vertex v at most once. A [g, f]-coloring is a generalized edge-coloring in which each color appears at each vertex v at least g(v) and at most f(v) ti...
详细信息
In an ordinary edge-coloring of a graph each color appears at each vertex v at most once. A [g, f]-coloring is a generalized edge-coloring in which each color appears at each vertex v at least g(v) and at most f(v) times, where g(v) and f(v) are respectively nonnegative and positive integers assigned to v. This paper gives a linear-time algorithm to find a [g, d]-coloring of a given partial k-tree using the minimum number of colors if there exists a [g, f]-coloring.
暂无评论