Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 8 of 8
Full-Text Articles in Computer Engineering
Faster Maximium Priority Matchings In Bipartite Graphs, Jonathan Turner
Faster Maximium Priority Matchings In Bipartite Graphs, Jonathan Turner
All Computer Science and Engineering Research
A maximum priority matching is a matching in an undirected graph that maximizes a priority score defined with respect to given vertex priorities. An earlier paper showed how to find maximum priority matchings in unweighted graphs. This paper describes an algorithm for bipartite graphs that is faster when the number of distinct priority classes is limited. For graphs with k distinct priority classes it runs in O(kmn1/2) time, where n is the number of vertices in the graph and m is the number of edges.
The Bounded Edge Coloring Problem And Offline Crossbar Scheduling, Jonathan Turner
The Bounded Edge Coloring Problem And Offline Crossbar Scheduling, Jonathan Turner
All Computer Science and Engineering Research
This paper introduces a variant of the classical edge coloring problem in graphs that can be applied to an offline scheduling problem for crossbar switches. We show that the problem is NP-complete, develop three lower bounds bounds on the optimal solution value and evaluate the performance of several approximation algorithms, both analytically and experimentally. We show how to approximate an optimal solution with a worst-case performance ratio of 3/2 and our experimental results demonstrate that the best algorithms produce results that very closely track a lower bound.
Maximum Priority Matchings, Jonathan Turner
Maximum Priority Matchings, Jonathan Turner
All Computer Science and Engineering Research
Let G=(V,E) be an undirected graph with n vertices and m edges, in which each vertex u is assigned an integer priority in [1,n], with 1 being the ``highest'' priority. Let M be a matching of G. We define the priority score of M to be an n-ary integer in which the i-th most-significant digit is the number of vertices with priority i that are incident to an edge in M. We describe a variation of the augmenting path method (Edmonds' algorithm) that finds a matching with maximum priority score in O(mn) time.
Conflict-Aware Real-Time Routing For Industrial Wireless Sensor-Actuator Networks, Chengjie Wu, Dolvara Gunatilaka, Mo Sha, Chenyang Lu
Conflict-Aware Real-Time Routing For Industrial Wireless Sensor-Actuator Networks, Chengjie Wu, Dolvara Gunatilaka, Mo Sha, Chenyang Lu
All Computer Science and Engineering Research
Process industries are adopting wireless sensor-actuator networks (WSANs) as the communication infrastructure. WirelessHART is an open industrial standard for WSANs that have seen world-wide deployments. Real-time scheduling and delay analysis have been studied for WSAN extensively. End-to-end delay in WSANs highly depends on routing, which is still open problem. This paper presents the first real-time routing design for WSAN. We first discuss end-to-end delays of WSANs, then present our real-time routing design. We have implemented and experimented our routing designs on a wireless testbed of 69 nodes. Both experimental results and simulations show that our routing design can improve the …
Maximizing Network Lifetime Of Wireless Sensor-Actuator Networks Under Graph Routing, Chengjie Wu, Dolvara Gunatilaka, Abusayeed Saifullah, Mo Sha, Paras Tiwari, Chenyang Lu, Yixin Chen
Maximizing Network Lifetime Of Wireless Sensor-Actuator Networks Under Graph Routing, Chengjie Wu, Dolvara Gunatilaka, Abusayeed Saifullah, Mo Sha, Paras Tiwari, Chenyang Lu, Yixin Chen
All Computer Science and Engineering Research
Process industries are adopting wireless sensor-actuator networks (WSANs) as the communication infrastructure. The dynamics of industrial environments and stringent reliability requirements necessitate high degrees of fault tolerance in routing. WirelessHART is an open industrial standard for WSANs that have seen world-wide deployments. WirelessHART employs graph routing schemes to achieve network reliability through multiple paths. Since many industrial devices operate on batteries in harsh environments where changing batteries are prohibitively labor-intensive, WSANs need to achieve long network lifetime. To meet industrial demand for long-term reliable communication, this paper studies the problem of maximizing network lifetime for WSANs under graph routing. We …
Woodstocc: Extracting Latent Parallelism From A Dna Sequence Aligner On A Gpu, Stephen V. Cole, Jacob R. Gardner, Jeremy D. Buhler
Woodstocc: Extracting Latent Parallelism From A Dna Sequence Aligner On A Gpu, Stephen V. Cole, Jacob R. Gardner, Jeremy D. Buhler
All Computer Science and Engineering Research
An exponential increase in the speed of DNA sequencing over the past decade has driven demand for fast, space-efficient algorithms to process the resultant data. The first step in processing is alignment of many short DNA sequences, or reads, against a large reference sequence. This work presents WOODSTOCC, an implementation of short-read alignment designed for Graphics Processing Unit (GPU) architectures. WOODSTOCC translates a novel CPU implementation of gapped short-read alignment, which has guaranteed optimal and complete results, to the GPU. Our implementation combines an irregular trie search with dynamic programming to expose regularly structured parallelism. We first describe this implementation, …
The Edge Group Coloring Problem With Applications To Multicast Switching, Jonathan Turner
The Edge Group Coloring Problem With Applications To Multicast Switching, Jonathan Turner
All Computer Science and Engineering Research
This paper introduces a natural generalization of the classical edge coloring problem in graphs that provides a useful abstraction for two well-known problems in multicast switching. We show that the problem is NP-hard and evaluate the performance of several approximation algorithms, both analytically and experimentally. We find that for random χ-colorable graphs, the number of colors used by the best algorithms falls within a small constant factor of χ, where the constant factor is mainly a function of the ratio of the number of outputs to inputs. When this ratio is less than 10, the best algorithms produces solutions that …
Grafalgo - A Library Of Graph Algorithms And Supporting Data Structures, Jonathan Turner
Grafalgo - A Library Of Graph Algorithms And Supporting Data Structures, Jonathan Turner
All Computer Science and Engineering Research
This report provides an overview of Grafalgo, an open-source library of graph algorithms and the data structures used to implement them. The programs in this library were originally written to support a graduate class in advanced data structures and algorithms at Washington University. Because the code's primary purpose was pedagogical, it was written to be as straightforward as possible, while still being highly efficient. Grafalgo is implemented in C++ and incorporates some features of C++11. The library is available on an open-source basis and may be downloaded from https://code.google.com/p/grafalgo/. Source code documentation is at www.arl.wustl.edu/~jst/doc/grafalgo. While not designed as production …