Bounded Degree Interval Sandwich Problems

The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous data. Most of the results obtained so far on the problems were hardness results. Here we study the problems under assumptions of sparseness, which hold in the biological context. We prove that both problems are polynomial when either (1) the input graph degree and the solution graph clique size are bounded, or (2) the solution graph degree is bounded. In particular, this implies that ICG is polynomial on bounded degree graphs for every fixed number of colors, in contrast with the recent result of Bodlaender and de Fluiter. Received October 2, 1997; revised April 1, 1998.     

An optimal algorithm for the angle-restricted all nearest neighborproblem on the reconfigurable mesh, with applications

Given a set S of n points in the plane and two directions r₁ and r₂, the Angle-Restricted All Nearest Neighbor problem (ARANN, for short) asks to compute, for every point p in S, the nearest point in S lying in the planar region bounded by two rays in the directions r₁ and r₂ emanating from p. The ARANN problem generalizes the well-known ANN problem and finds applications to pattern recognition, image processing, and computational morphology. Our main contribution is to present an algorithm that solves an instance of size n of the ARANN problem in O(1) time on a reconfigurable mesh of size n×n. Our algorithm is optimal in the sense that Ω(n²) processors are necessary to solve the ARANN problem in O(1) time. By using our ARANN algorithm, we can provide O(1) time solutions to the tasks of constructing the Geographic Neighborhood Graph and the Relative Neighborhood Graph of n points in the plane on a reconfigurable mesh of size n×n. We also show that, on a somewhat stronger reconfigurable mesh of size n×n², the Euclidean Minimum Spanning Tree of n points can be computed in O(1) time     

Computing the hyperbolicity constant of a cubic graph

In this paper we obtain information about the hyperbolicity constant of cubic graphs. They are a very interesting class of graphs with many applications; furthermore, they are also very important in the study of Gromov hyperbolicity, since for any graph G with bounded maximum degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. We find some characterizations for the cubic graphs which have small hyperbolicity constants, i.e. the graphs which are like trees (in the Gromov sense). Besides, we obtain bounds for the hyperbolicity constant of the complement graph of a cubic graph; our main result of this kind says that for any finite cubic graph G which is not isomorphic either to K₄ or to K_{3, 3}, the inequalities 5k/4≤δ (?)≤3k/2 hold, if k is the length of every edge in G.     

Honeycomb networks: Topological properties and communicationalgorithms

The honeycomb mesh, based on hexagonal plane tessellation, is considered as a multiprocessor interconnection network. A honeycomb mesh network with n nodes has degree 3 and diameter ≈1.63√n-1, which is 25 percent smaller degree and 18.5 percent smaller diameter than the mesh-connected computer with approximately the same number of nodes. Vertex and edge symmetric honeycomb torus network is obtained by adding wraparound edges to the honeycomb mesh. The network cost, defined as the product of degree and diameter, is better for honeycomb networks than for the two other families based on square (mesh-connected computers and tori) and triangular (hexagonal meshes and tori) tessellations. A convenient addressing scheme for nodes is introduced which provides simple computation of shortest paths and the diameter. Simple and optimal (in the number of required communication steps) routing, broadcasting, and semigroup computation algorithms are developed. The average distance in honeycomb torus with n nodes is proved to be approximately 0.54√n. In addition to honeycomb meshes bounded by a regular hexagon, we consider also honeycomb networks with rhombus and rectangle as the bounding polygons     

An improved simulation of space and reversal bounded deterministic turing machines by width and depth bounded uniform circuits

We present an improved simulation of space and reversal bounded Turing machines by width and depth bounded uniform circuits. (All resource bounds hold simultaneously.) An S(n) space, R(n) reversal bounded deterministic k-tape Turing machine can be simulated by a uniform circuit of O(R(n)log²S(n)) depth and O(S(n)^k) width. Our proof is cleaner, and has slightly better resource bounds than the original proof due to Pippenger (1979). The improvement is resource bounds comes primarily from the use of a shared-memory machine instead of an oblivious Turing machine, and the concept of a ‘special situation’.     

平面有界闭区域图形的拓扑分类识别

本文首先将具有简单封闭曲线特征的闭主曲线学习算法应用于平面有界闭区域图形的边界提取,给出相应的算法。结合拓扑度理论,本文还定义了有界闭区域的边界关联矩阵,引入了平面中图像的F-同胚概念,运用边界关联矩阵是F-同胚下的完全不变量原理,将F-同胚和边界关联矩阵概念有机结合起来,对平面有界区域图形进行拓扑粗分类,以达到缩小搜索范围、提高搜索速度的目的。最后,本文给出了平面有界闭区域图形的计算机拓扑识别的算法及其实现。     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log² n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.This research was supported by NSF Grants CCR-9011214 and CCR-9205982.     

The bounded degree problem for NLC grammars is decidable

The degree of a graph H is the maximum among the degrees of its nodes. A set of graphs L is of bounded degree if there exists a positive integer n such that the degree of each graph in L does not exceed n. We demonstrate that it is decidable whether or not the (graph) language of an arbitrary node label controlled (NLC) grammar is of bounded degree. Moreover, it is shown that, given an arbitrary NLC grammar G generating the language L(G) of bounded degree, one can effectively compute the maximum integer which appears as the degree of a graph in L(G).     

Sum Coloring of Bipartite Graphs with Bounded Degree

We consider the Chromatic Sum Problem on bipartite graphs which appears to be much harder than the classical Chromatic Number Problem. We prove that the Chromatic Sum Problem is NP-complete on planar bipartite graphs with $\Delta \leq 5$, but polynomial on bipartite graphs with $\Delta \leq 3$, for which we construct an $O(n^{2})$-time algorithm. Hence, we tighten the borderline of intractability for this problem on bipartite graphs with bounded degree, namely: the case $\Delta =3$ is easy, $% \Delta =5$ is hard. Moreover, we construct a $27/26$-approximation algorithm for this problem thus improving the best known approximation ratio of $10/9$.     

限制树宽图上的有界聚类

有界聚类问题源于II3M研究院开发的一个分布式流处理系统,即S系统。问题的输入是一个点赋权和边赋权的无向图,并指定若干个称为终端的顶点。称顶点集合的一个子集为一个子类。子类中所有顶点的权和加上该子类边界上所有边的权和称为该子类的费用。有界聚类问题是要得到所有顶点的一个聚类,要求每个子类的费用不超过给定预算召,每个子类至多包含一个终端,并使得所有子类的总费用最小。对于限制树宽图上的有界聚类问题,给出了拟多项式时间精确算法。利用取整的技巧对该算法进行修正,可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(1+ε)B,:是任意小的正数。如果进一步要求每个子类恰好包含一个终端,则所给算法可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(2+ε)B。     

Efficient generation of plane trees

A rooted plane tree is a rooted tree with a left-to-right ordering specified for the children of each vertex. In this paper we give a simple algorithm to generate all rooted plane trees with at most n vertices. The algorithm uses O(n) space and generates such trees in O(1) time per tree without duplications. The algorithm does not output entire trees but the difference from the previous tree. By modifying the algorithm we can generate without duplications all rooted plane trees having exactly n vertices in O(1) time per tree, all rooted plane trees having at most n vertices with maximum degree at most D in O(1) time per tree, and all rooted plane trees having exactly n vertices including exactly c leaves in O(n−c) time per tree. Also we can generate without duplications all (non-rooted) plane trees having exactly n vertices in O(n³) time per tree.     

Algorithms for Graphs Embeddable with Few Crossings per Edge

We consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum independent set, minimum vertex cover, minimum dominating set and many others, admit polynomial time approximation schemes when restricted to such graphs. This extends previous results by Baker and Eppstein to a much broader class of graphs. We also prove that for the considered class of graphs, there are balanced separators of size where n is a number of vertices in the graph. On the negative side, we prove that it is intractable to recognize the graphs embeddable in the plane with at most one crossing per edge.     

A note on the expected time required to construct the outer layer

The expected time E(T) of the standard divide-and-conquer algorithm for finding the outer layer of a set of points in the plane depends upon the distribution of the points. Under the mild assumption that the points are independent random vectors and have a common bounded density with compact support, it is shown that E(T) = O(n).     

Lower bounds for sense of direction in regular graphs

A graph G with n vertices and maximum degree cannot be given weak sense of direction using less than colours. It is known that n colours are always sufficient, and it was conjectured that just are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring more colours than . In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that colours are necessary, where d _G is the degree of G.Received: April 2002, Accepted: April 2003, Sebastiano Vigna: Partially supported by the Italian MURST (Finanziamento di iniziative di ricerca diffusa condotte da parte di giovani ricercatori).The results of this paper appeared in a preliminary form in Distributed Computing. 14th International Conference, DISC 2000, Springer-Verlag, 2000.     

Globally asymptotically stable saturated PID controllers for a double integrator with constant disturbance

This paper provides a deep insight into the saturated PID control of a double integrator with bounded disturbance. On the basis of the nested saturation functions, a simple PID‐like controller is proposed. The main difficulty in saturation control with bounded disturbances is to prove that the unsaturated regions are invariant. By phase plane and singular perturbation analysis, we prove that the saturation restrictions on the controller can be removed one by one in finite time, and the closed‐loop system can be finally reduced to a nonsaturated PID controlled double integrator. The sufficient conditions for the stability of the closed loop with disturbance are also derived. Finally, numerical simulations are conducted to validate the effectiveness of the proposed control scheme. Copyright © 2012 John Wiley & Sons, Ltd.     

Constructing the visibility graph for n-line segments in O(n2) time

Given a set S of line segments in the plane, its visibility graph G_S is the undirected graph which has the endpoints of the line segments in S as nodes and in which two nodes (points) are adjacent whenever they ‘see’ each other (the line segments in S are regarded as nontransparent obstacles). It is shown that G_S can be constructed in O(n²) time and space for a set S of n nonintersecting line segments. As an immediate implication, the shortest path between two points in the plane avoiding a set of n nonintersecting line segments can be computed in O(n²) time and space     

2m次Bèzier曲线自适应降次逼近算法

给出了封闭的2m次Bèzier曲线的降次逼近公式,并讨论了相应的逼近误差。文章工作除了具有传统的端点约束、C1—约束外,还具有以下特点:首先,基于欧几里德范数讨论逼近误差,更加符合人们的认识;其次,对于分段降阶逼近的情形,首先考虑并采用了选择拐点的策略;第三,考虑并采用了选择极大值点的策略。大量数值试验表明:第二、三两条策略的采用可以在很大程度上减少了2m-1次Bèzier曲线段达到逼近2m次Bèzier平面曲线的容差要求。     

On approximating the longest path in a graph

We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the problem of finding a path of lengthn-n ^ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration ^δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of , for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs. D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation. Communicated by M. X. Goemans.