This book contains Volume 7 of the Journal of graph algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, im...
详细信息
ISBN:
(数字)9789812773296
ISBN:
(纸本)9789812568441;9789812773296
This book contains Volume 7 of the Journal of graph algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit *** algorithms and Applications 4 presents contributions from prominent authors and includes selected papers from (a) the Seventh International Workshop on algorithms and Data Structures (WADS 2001) and (b) the 2001 Symposium on graph Drawing (GD 2001). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
An outerplanar graph is a graph that can be embedded on the plane such that all the vertices lie on the exterior face and no two edges intersect except possibly at a common end-vertex. Five sequential algorithms had b...
详细信息
An outerplanar graph is a graph that can be embedded on the plane such that all the vertices lie on the exterior face and no two edges intersect except possibly at a common end-vertex. Five sequential algorithms had been proposed for rec ognizing outerplanar graph in the literature and all run in linear time and space. Although among them, the algorithms of Mitchell, Wiegers, and Tsin and Lin are obviously superior, no efforts had been made in comparing their performances during run-time. In this thesis, the aforementioned three algorithms are implemented and their performances are compared using a large number of randomly generated graphs. Furthermore, the algorithms of Mitchell and Wiegers are modified so that an out- erpalnar embedding is generated if the input graph is outerplanar. Correctness proofs of the modification are presented. It is also shown that the complexity of the modified algorithms remain linear in both time and space.
SuiteSparse:graphBLAS is a full parallel implementation of the graphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and...
详细信息
SuiteSparse:graphBLAS is a full parallel implementation of the graphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. A description of the parallel implementation of SuiteSparse:graphBLAS is given, including its novel parallel algorithms for sparse matrix multiply, addition, element-wisemultiply, submatrix extraction and assignment, and the graphBLAS mask/accumulator operation. Its performance is illustrated by solving the graph problems in the GAP Benchmark and by comparing it with other sparse matrix libraries.
Spatio-temporal coding that combines spatial constraints with temporal sequencing is of great interest to brain-like circuit modelers. In this paper we present some new ideas of how these types of circuits can self-or...
详细信息
Spatio-temporal coding that combines spatial constraints with temporal sequencing is of great interest to brain-like circuit modelers. In this paper we present some new ideas of how these types of circuits can self-organize, We introduce a temporal correlation rule based on the time difference between the firings of neurons. With the aid of this rule we show an analogy between a graph and a network of spiking neurons, The shortest path, clustering based on the nearest neighbor, and the minimal spanning tree algorithms are solved using the proposed approach.
Consumer power demand is an ever increasing component in distribution networks. A solution to meet this bridge between conventional source availability and load demands is using microgrids. The microgrid is an assortm...
详细信息
Consumer power demand is an ever increasing component in distribution networks. A solution to meet this bridge between conventional source availability and load demands is using microgrids. The microgrid is an assortment of loads and distributed generators (DGs). The dynamicity of microgrids is a key challenge for protection engineers. The purpose of this paper is to develop a central protection system (CPS) for a microgrid with fuzzy based monitoring and graph algorithms based protection control features. Hence the CPS provides suitable overcurrent relay coordination to the microgrid which may cause minimum portion of the network disconnection.
The main goal of this work is to demonstrate that the development of data-intensive applications for vector systems is not only important and interesting, but is also very possible. In this paper we describe possible ...
详细信息
This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, t...
详细信息
This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. The first part of the dissertation addresses a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A.-approximation algorithm for ATSP is one that runs in polynomial time and always produces a tour at most. times longer than the shortest tour. Finding such an algorithm with constant rho had been a long-standing open problem. Here we give such an algorithm. The second part of the dissertation addresses the perfect matching problem. We have known since the 1980s that it has efficient parallel algorithms if the use of randomness is allowed. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. We show that it is in the class quasi-NC. That is, we give a deterministic parallel algorithm that runs in poly-logarithmic time on quasi-polynomially many processors.
We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based ...
详细信息
We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n(2)) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. [7] have been considered to be the most efficient on the LARPBS model till now. Their algorithm [7] for these two problems require O(log n) time and O(n(3)/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n(2)) processors. No previous algorithm was known for these latter problems on the LARPBS.
The fixed-time constrainted routing problem (FTCRP) is an engineering variant of the multicommodity network-flow problem where flows represent unsplittable telecommunication routes, and global solutions should be comp...
详细信息
ISBN:
(纸本)9781467387224
The fixed-time constrainted routing problem (FTCRP) is an engineering variant of the multicommodity network-flow problem where flows represent unsplittable telecommunication routes, and global solutions should be computed in at most one millisecond per route. Algorithmic solutions based on integer linear programming (ILP) lead to column generation (CG) heuristics to cope lazily with the exponential number of paths. In this paper we present experimental evidence that solving FTCRP with ILP leads to explosive time and memory consumption, while many innovative algorithms can alleviate this combinatorial explosion, and are also amenable to highly scalable bulk-synchronous (BSP) algorithms. We show several new solution methods tested on realistic instances with up to hundreds of thousands of routes and many dozens of computational cores with high efficiency.
Multi-core machines are becoming widely used which, as a consequence, forces parallel computing to move from research labs to being adopted everywhere. Due to the fact that developing parallel code is a significantly ...
详细信息
ISBN:
(纸本)9781920682880
Multi-core machines are becoming widely used which, as a consequence, forces parallel computing to move from research labs to being adopted everywhere. Due to the fact that developing parallel code is a significantly complex process, the main focus of today's research is to design tools which facilitate the process of parallelising code. The Parallel Iterator (PI) is a tool which was developed to automate the process of parallelising loops in 00 applications. graph algorithms can be represented using objects and hence they are excellent use cases for the PI. This paper discusses using the PI to parallelising graph algorithms such as breadth-first search (BFS), depth-first search (DFS) and minimum spanning tree (MST). Using the PI to parallelise such graph algorithms required adding some adaptations to the current concept of the PI to handle certain graph algorithms. The PI facilitates the process of parallelising graph algorithms in a way which keeps the parallel code readable and maintainable while exhibiting speedup. Java was used as the implementation language since it is one of the most commonly used object oriented languages. The parallelised graph algorithms were tested on different graphs and trees with different densities, granularity and structures. The experimental results show that the parallelised graph algorithms exhibit good speedups.
暂无评论