Search

Given a graph G = ( V , E ) of order n and maximum degree Δ , the NP -complete S - labeling problem consists in finding a labeling of G , i.e. a bijective mapping ϕ : V → { 1 , 2 … n } , such that SL ϕ ( G ) = ∑ u v ∈ E min { ϕ ( u ) , ϕ ( v ) } is minimized. In this paper, we study the S - labeling problem, with a particular focus on algorithmic issues. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then provide lower bounds on SL ϕ ( G ) , together with a generic greedy algorithm, which collectively allow us to approximate the problem in several classes of graphs—in particular, we obtain constant approximation ratios for regular graphs and bounded degree graphs. We also show that deciding whether there exists a labeling ϕ of G such that SL ϕ ( G ) ≤ | E | + k is solvable in O ∗ ( 2 2 k ( 2 k ) ! ) time, thus fixed-parameterized tractable in k . We finally show that the S - Labeling problem is polynomial-time solvable for two classes of graphs, namely split graphs and (sets of) caterpillars. [ABSTRACT FROM AUTHOR]

In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graph data. This paper investigates the problem of mining uncertain graph data and especially focuses on mining frequent subgraph patterns on an uncertain graph database. A novel model of uncertain graphs is presented, and the frequent subgraph pattern mining problem is formalized by introducing a new measure, called expected support. This problem is proved to be NP-hard. An approximate mining algorithm is proposed to find a set of approximately frequent subgraph patterns by allowing an error tolerance on expected supports of discovered subgraph patterns. The algorithm uses efficient methods to determine whether a subgraph pattern can be output or not and a new pruning method to reduce the complexity of examining subgraph patterns. Analytical and experimental results show that the algorithm is very efficient, accurate, and scalable for large uncertain graph databases. To the best of our knowledge, this paper is the first one to investigate the problem of mining frequent subgraph patterns from uncertain graph data. [ABSTRACT FROM AUTHOR]

This paper deals with a special kind of complex systems which depend on an arbitrary (and usually large) number n of random Boolean variables. The so-called complex stochastic Boolean systems often appear in many different scientific, technical or social areas. Clearly, there are 2n binary states associated to such a complex system. Each one of them is given by a binary string u = (u1,...,un) ∈ {0, 1}n of n bits, which has a certain occurrence probability Pr{u}. The behavior of a complex stochastic Boolean system is determined by the current values of its 2n binary n-tuple probabilities Pr{u} and by the ordering between pairs of them. Hence, the intrinsic order graph provides a useful representation of these systems by displaying (scaling) the 2n binary n-tuples which are ordered in decreasing probability of occurrence. The intrinsic order reduces the complexity of the problem from exponential (2n binary n-tuples) to linear (n Boolean variables). For any fixed binary n-tuple u, this paper presents a new, simple algorithm enabling rapid, elegant determination of all the binary n-tuples v with occurrence probabilities less than or equal to (greater than or equal to) Pr{u}. This algorithm is closely related to the lexicographic (truth-table) order in {0, 1}n, and this is illustrated through the connections (paths) in the intrinsic order graph. [ABSTRACT FROM AUTHOR]

This paper discusses the hierarchical properties of digraphs and proposes flowchart decomposition algorithms using these properties. The hierarchical structure discussed here is based on only the topological relation- skips between vertices and the inclusive relationship among sets of vertices. When the given flowchart represents the control flow of a computer program, this hierarchical structure also shows strong correspondence between these inclusive relationships and program modules. The proposed flowchart decomposition algorithm consists of one algorithm for detecting modules and another algorithm for further decomposing the detected modules. This paper focuses on the former algorithm. Because the hierarchical structure discussed in this paper corresponds to the traditional program modules (e.g., function or procedure) of most of the computer programming languages, the module-detection algorithm can be used not only for decomposing flowchart but for more general purposes, including module design. Two types of module-detection algorithm are discussed in this paper. One detects all modules, and the other detects a restricted subset of modules from the standpoint of flow-chart decomposition. We then demonstrate with a practical example that the latter algorithm is ten times faster than the former. [ABSTRACT FROM AUTHOR]

A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple-free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes a fast algorithm to enumerate all convex subgraphs that satisfy the 110 constraints from the dataflow graph (DFG) of a basic block. The algorithm can be tuned to determine all subgraphs or only those connected subgraphs. This allows a choice between better instruction-set extension (ISE) and faster design space exploration. The algorithm uses a grading method to identify the next node for inclusion into a subgraph. If the selected node is included, other related nodes are included as well, thus ensuring that the resultant subgraph is always convex and at the same time, reducing the problem size by a block of nodes. If the selected node is not included, the DFG will be split into smaller DFGs, thus reducing also the problem size. With this as base, the algorithm employs a simple but efficient method to prune the invalid subgraphs that violate the 110 constraints. Results show that for relatively small DFGs with small exploration space, the new algorithm has similar runtimes to that of existing algorithms. However, for larger DFGs with much larger exploration space and with multiple input and output constraints, the runtime improvement can be orders of magnitude better than that of existing algorithms. The new algorithm can be used to quickly identify custom instructions for ISE of embedded processors. [ABSTRACT FROM AUTHOR]

A realizer of a triangulated plane graph G is a partition of interior edges of G, satisfying some conditions. The realizer has many applications, including graph drawing algorithms. Given a triangulated plane graph G, no algorithm to generate all realizers of G is known. In this paper, we first give an algorithm to generate all realizers. We first define a left canonical ordering for the vertices of an input graph, then show that there is a bijection between the left canonical orderings and realizers. Based on the bijection, we give an algorithm to generate all realizers. The algorithm generates each realizer in O(n) time without duplications, where n is the number of vertices in the graph. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 89(7): 40–47, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20276 [ABSTRACT FROM AUTHOR]

A drawing of a plane graph is called an inner rectangular drawing if every edge is drawn as a horizontal or vertical line segment so that every inner face is a rectangle. In this paper we show that a plane graph G has an inner rectangular drawing D if and only if a new bipartite graph constructed from G has a perfect matching. We also show that D can be found in time O(n1.5/ log n) if G has n vertices and a sketch of the outer face is prescribed, that is, all the convex outer vertices and concave ones are prescribed. [ABSTRACT FROM AUTHOR]

Abstract: In this paper a new hierarchical extension of the algorithm for robot path planning is introduced. The hierarchical algorithm uses a down-top strategy and a set of precalculated paths (materialization of path costs) in order to improve performance. This on-line path planning algorithm allows optimality and specially lower computational time. H-Graphs (hierarchical graphs) are modified and adapted to support on-line path planning with materialization of costs and multiple hierarchical levels. Traditional on-line robot path planning focused in horizontal spaces is also extended to vertical and interbuilding spaces. Some experimental results are showed and compared to other path planning algorithms. [Copyright &y& Elsevier]

Let G be a graph. A component of G is a maximal connected subgraph in G. A vertex v is a cut vertex of G if κ(G-v) > κ(G), where κ(G) is the number of components in G. Similarly, an edge e is a bridge of G if κ(G-e) > κ(G). In this paper, we will propose new O(n) algorithms for finding cut vertices and bridges of a trapezoid graph, assuming the trapezoid diagram is given. Our algorithms can be easily parallelized on the EREW PRAM computational model so that cut vertices and bridges can be found in O(logn) time by using O(n/logn) processors. [ABSTRACT FROM AUTHOR]

In this paper we present an algorithm for determining satisfiability of general Boolean formulas which are not necessarily in conjunctive normal form. The algorithm extends the well-known Davis–Putnam algorithm to work on Boolean formulas represented using Boolean Expression Diagrams (BEDs). The BED data structure allows the algorithm to take advantage of the built-in reduction rules and the sharing of sub-formulas. Furthermore, it is possible to combine the algorithm with traditional BDD construction (using Bryant’s Apply-procedure). By adjusting a single parameter to the BedSat algorithm, it is possible to control to what extent the algorithm behaves like the Apply-algorithm or like a SAT-solver. Thus, the algorithm can be seen as bridging the gap between standard SAT-solvers and BDDs. We present promising experimental results for 566 non-clausal formulas obtained from the multi-level combinational circuits in the ISCAS’85 benchmark suite and from performing model checking of a shift-and-add multiplier. [ABSTRACT FROM AUTHOR]

For an arbitrary fixed surface S, a linear time algorithm is presented that for a given graph G either finds an embedding of G in S or identifies a subgraph of G that is homeomorphic to a minimal forbidden subgraph for embeddability in S. A side result of the proof of the algorithm is that minimal forbidden subgraphs for embeddability in S cannot be arbitrarily large. This yields a constructive proof of the result of Robertson and Seymour that for each closed surface there are only finitely many minimal forbidden subgraphs. The results and methods of this paper can be used to solve more general embedding extension problems. [ABSTRACT FROM AUTHOR]

Various algorithms have been proposed for the problem of drawing rooted ordered trees. As one of them, Unno and colleagues [1] presented an O(n3) time algorithm that (1) produces an initial drawing of a given tree T, and then (2) finds a narrower drawing by repeatedly moving subtrees (n is the number of nodes in T). In this paper, we show that the same drawing can be obtained more efficiently by maintaining the contours of subtrees. If a natural restriction is imposed on the sizes of nodes, our method can be executed in a time O(n·α(n, n)), where α is a functional inverse of Ackermann's function. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(5): 31–41, 1997 [ABSTRACT FROM AUTHOR]