Performance improvement and limitations in extremum seeking control

We propose the inclusion of a dynamic compensator in the extremum seeking algorithm which improves the stability and performance properties of the method. This compensator is added to the integrator used for adaptation to improve the overall relative degree and phase response of the extremum seeking loop. The compensator is potentially more effective in accounting for the plant dynamics than the often used phase shifting of the demodulation signal. We present a detailed analysis of the extremum seeking system based on averaging. This analysis provides two linear models, one for tracking reference changes and the other for sensitivity to noise, which offer insight into how different parameters influence the performance. This analysis is less conservative than in previous cases and allows the use of faster adaptation for improved transients. We extend the extremum seeking method to problems of tracking changes in the set point which are more general than step functions.     

Efficient parallel algorithms for breadth first spanning forests of general graphs

Ghosh and Bhattacharjee propose [2] (Intern. J. Computer Math., 1984, Vol. 15, pp. 255-268) an algorithm of determining breadth first spanning trees for graphs, which requires that the input graphs contain some vertices, from which every other vertex in the input graph can be reached. These vertices are called starting vertices. The complexity of the GB algorithm is O(log² n) using O{n ³) processors. In this paper an algorithm, named BREADTH, also computing breadth first spanning trees, is proposed. The complexity is O(log² n) using O{n ³/logn) processors. Then an efficient parallel algorithm, named- BREADTHFOREST, is proposed, which generalizes algorithm BREADTH. The output of applying BREADTHFOREST to a general graph, which may not contain any starting vertices, is a breadth first spanning forest of the input graph. The complexity of BREADTHFOREST is the same as BREADTH.     

Distributed extremum seeking and formation control for nonholonomic mobile network

In this paper, an integrated control and optimization problem is studied in the context of formation and coverage of a cluster of nonholonomic mobile robots. In particular, each communication channel is modeled by its outage probability, and hence, connectivity is maintained if the outage probability is less than a certain threshold. The objective of the communication network is to not only maintain resilient communication quality but also extend the network coverage. An information theory based performance index is defined to quantify this control objective. Unlike most of the existing results, the proposed cooperative control design does not assume the knowledge of any gradient (of the performance index). Rather, a distributed extremum seeking algorithm is designed to optimize the connectivity and coverage of the mobile network. The proposed approach retains all the advantages of cooperative control, and it can not only perform extremum seeking individually, but also ensures a consensus of estimates between any pair of connected systems. Simulation results demonstrate effectiveness of the proposed methodology.     

The super spanning connectivity and super spanning laceability of the enhanced hypercubes

A k -container C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k ^* -container if it contains all vertices of G. A graph G is k ^* -connected if there exists a k ^*-container between any two distinct vertices of G. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k ^*-container between any two distinct vertices of G for every k with 1≤k≤κ(G) where κ(G) is the connectivity of G. A bipartite graph G is k ^* -laceable if there exists a k ^*-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k ^*-container between any two vertices from different partite set of G for every k with 1≤k≤κ(G). In this paper, we prove that the enhanced hypercube Q _n,m is super spanning laceable if m is an odd integer and super spanning connected if otherwise.

Unified frameworks for sampled-data extremum seeking control: Global optimisation and multi-unit systems

Two frameworks are proposed for extremum seeking of general nonlinear plants based on a sampled-data control law, within which a broad class of nonlinear programming methods is accommodated. It is established that under some generic assumptions, semi-global practical convergence to a global extremum can be achieved. In the case where the extremum seeking algorithm satisfies a stronger asymptotic stability property, the converging sequence is also shown to be stable using a trajectory-based proof, as opposed to a Lyapunov-function-type approach. The former is more straightforward and insightful. This allows for more general optimisation algorithms than considered in existing literature, such as those which do not admit a state-update realisation and/or Lyapunov functions. Lying at the heart of the analysis throughout is robustness of the optimisation algorithms to additive perturbations of the objective function. Multi-unit extremum seeking is also investigated with the objective of accelerating the speed of convergence.     

On plane spanning trees and cycles of multicolored point sets with few intersections

Let P₁,…,Pk be a collection of disjoint point sets in R² in general position. We prove that for each 1?i?k we can find a plane spanning tree Ti of Pi such that the edges of T₁,…,Tk intersect at most , where n is the number of points in P₁∪?∪Pk. If the intersection of the convex hulls of P₁,…,Pk is nonempty, we can find k spanning cycles such that their edges intersect at most (k−1)n times, this bound is tight. We also prove that if P and Q are disjoint point sets in general position, then the minimum weight spanning trees of P and Q intersect at most 8n times, where |P∪Q|=n (the weight of an edge is its length).     

Hierarchical spanning trees and distributing on incomplete hypercubes

Incomplete hypercubes are gaining increasing attention as one of the possible solutions for the limitation on the number of nodes in the hypercubes. Distributing, in which one node sends distinct messages to distinct nodes, and its reverse operation are frequently used operations on data parallel computation. In this paper, we propose two types of spanning trees in incomplete hypercubes (composed of an n-cube and a k-cube): the binomial hierarchical spanning tree-binomial HST, and the balanced hierarchical spanning tree-balanced HST, for distributing (and its reverse operation). Distributing algorithms based on a balanced HST take better advantage of overlap between communication ports, or have speedup up to k/2 or n/2 over that based on the binomial HST when concurrently communication on all ports are possible, from the view point of communication complexity. An algorithm to construct hierarchical spanning trees in general incomplete hypercubes, which consist of an arbitrary number of nodes, is also devised.     

Balancing minimum spanning trees and shortest-path trees

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and a>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+2 times the shortest-path distance, and yet the total weight of the tree is at most 1+2/ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex.Current research supported by NSF Research Initiation Award CCR-9307462. This work was done while this author was supported by NSF Grants CCR-8906949, CCR-9103135, and CCR-9111348.Part of this work was done while this, author was at the University of Maryland Institute for Advanced Computer Studies (UMIACS) and supported by NSF Grants CCR-8906949 and CCR-9111348.     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

On finding optimal and near-optimal lineal spanning trees

The search for good lineal, or depth-first, spanning trees is an important aspect in the implementation of a wide assortment of graph algorithms. We consider the complexity of findingoptimal lineal spanning trees under various notions of optimality. In particular, we show that several natural problems, such as constructing a shortest or a tallest lineal tree, are NP-hard. We also address the issue of polynomial-time, near-optimization strategies for these difficult problems, showing that efficient absolute approximation algorithms cannot exist unlessP = NP.This author's research was supported in part by the Sandia University Research Program and by the National Science Foundation under Grant M IP-8603879.This author's research was supported in part by the National Science Foundation under Grants ECS-8403859 and MIP-8603879.     

Min‐degree constrained minimum spanning tree problem: complexity,properties, and formulations

This paper addresses a new combinatorial problem, the Min‐Degree Constrained Minimum Spanning Tree (md‐MST), that can be stated as: given a weighted undirected graph with positive costs on the edges and a node‐degrees function , the md‐MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of or is a leaf node. This problem is closely related to the well‐known Degree Constrained Minimum Spanning Tree (d‐MST) problem, where the degree constraint is an upper bound instead. The general NP‐hardness for the md‐MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow‐based formulations are proposed and computational experiments involving the associated Linear Programming (LP) relaxations are presented.     

Modeling and solving the rooted distance-constrained minimum spanning tree problem

In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)$G=(V,E)$ with node set V={0,1,…,n}$V=\{0,1,\dots ,n\}$ and edge set E$E$, two integer weights, a cost _ce$c_e$ and a delay _we$w_e$ associated with each edge e$e$ of E$E$, and a natural (time limit) number H$H$, we wish to find a spanning tree T$T$ of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than H$H$. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.     

A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality. It can also be used to analyze the sensitivity of a single-source shortest-path tree to changes in edge costs, and to analyze the sensitivity of a minimum-cost network flow. The algorithm is simple and practical. It uses the properties of a planar embedding, combined with a heap-ordered queue data structure.This research was partially supported by Office of Naval Research Grant N00014-87-K-0467 and National Science Foundation Grant CCR-8610181.This research was done while the author was at the Department of Computer Science, Princeton University, Princeton, NJ 08544, USA.This research was done while the author was at the Department of Computer Science, Stanford University, Stanford, CA 94305, USA.     

基于GPU的并行最小生成树算法的设计与实现*

针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的minreduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语缩短关键步骤的查找时间,从而获得较高效率。实验表明,相对于传统CPU实现算法和不使用原语的算法,该算法具有较明显的性能优势。     

Coupled region-edge shape priors for simultaneous localization and figure-ground segmentation

We propose a new algorithm for simultaneous localization and figure-ground segmentation where coupled region-edge shape priors are involved with two different but complementary roles. We resort to a segmentation-based hypothesis-and-test paradigm in this research, where the region prior is used to form a segmentation and the edge prior is used to evaluate the validity of the formed segmentation. Our fundamental assumption is that the optimal shape-constrained segmentation that maximizes the agreement with the edge prior occurs at the correctly hypothesized location. Essentially, the proposed algorithm addresses a mid-level vision issue that aims at producing a map image for part detection useful for high-level vision tasks. Our experiments demonstrated that this algorithm offers promising results in terms of both localization and segmentation.     

Laplacian spectrum analysis and spanning tree algorithm for circuit partitioning problems

The spectrum of a graph is the set of all eigenvalues of the Laplacian matrix of the graph. There is a closed relationship between the Laplacian spectrum of graphs and some properties of graphs such as connectivity. In the recent years Laplacian spectrum of graphs has been widely applied in many fields. The application of Laplacian spectrum of graphs to circuit partitioning problems is reviewed in this paper. A new criterion of circuit partitioning is proposed and the bounds of the partition ratio for weighted graphs are also presented. Moreover, the deficiency of graph-partitioning algorithms by Laplacian eigenvectors is addressed and an algorithm by means of the minimal spanning tree of a graph is proposed. By virtue of taking the graph structure into consideration this algorithm can fulfill general requirements of circuit partitioning.