Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Physical Sciences and Mathematics (825)
- Computer Engineering (733)
- Computer Sciences (730)
- Mechanical Engineering (376)
- Biomedical Engineering and Bioengineering (211)
-
- Electrical and Computer Engineering (127)
- Chemical Engineering (88)
- Life Sciences (76)
- Materials Science and Engineering (62)
- Civil and Environmental Engineering (53)
- Bioimaging and Biomedical Optics (51)
- Environmental Engineering (51)
- Electrical and Electronics (49)
- Physics (47)
- Aerospace Engineering (42)
- Medicine and Health Sciences (35)
- Engineering Science and Materials (34)
- Optics (34)
- Mechanics of Materials (30)
- Chemistry (26)
- Nanoscience and Nanotechnology (25)
- Aerodynamics and Fluid Mechanics (24)
- Neuroscience and Neurobiology (24)
- Molecular, Cellular, and Tissue Engineering (17)
- Biochemistry, Biophysics, and Structural Biology (16)
- Biomedical (16)
- Artificial Intelligence and Robotics (15)
- Medical Specialties (15)
- Applied Mathematics (14)
- Keyword
-
- CFD (17)
- Machine learning (17)
- Optimization (16)
- Machine Learning (11)
- Microfluidics (10)
-
- Fluorescence (9)
- Imaging (9)
- Mems411 (9)
- Biomaterials (8)
- Cancer (8)
- FPGA (8)
- Image reconstruction (8)
- Polarization (8)
- Aerosol (7)
- Biomechanics (7)
- Cyanobacteria (6)
- Deep Learning (6)
- Deep learning (6)
- Lignin (6)
- Mechanobiology (6)
- Nanoparticles (6)
- Nucleation (6)
- Acoustofluidics (5)
- Computational Fluid Dynamics (5)
- Computational imaging (5)
- Computed tomography (5)
- Control (5)
- Focused ultrasound (5)
- Metabolic Engineering (5)
- Metabolic engineering (5)
- Publication Year
- Publication
-
- McKelvey School of Engineering Graduate Student Theses & Dissertations (783)
- All Computer Science and Engineering Research (683)
- Mechanical Engineering Design Project Class (242)
- Washington University / UMSL Mechanical Engineering Design Project JME 4110 (40)
- All Theses and Dissertations (ETDs) (36)
-
- Electrical & Systems Engineering Publications and Presentations (23)
- Computer Science and Engineering Faculty Research (3)
- Electrical and Systems Engineering Capstone Design Projects (3)
- Generative AI Teaching Activities (3)
- Undergraduate Research Symposium Posters (3)
- Olin Business School Graduate Student Theses and Dissertations (2)
- Books and Monographs (1)
- Doctor of Business Administration Dissertations (1)
- ENGR 310: Technical Writing Final Project (1)
- Graduate School of Architecture & Urban Design Theses & Dissertations (1)
- Mathematics Faculty Research (1)
- Senior Honors Papers / Undergraduate Theses (1)
- WashU Libraries Presentations (1)
- Publication Type
- File Type
Articles 991 - 1020 of 1828
Full-Text Articles in Engineering
Revelation Of Yin-Yang Balance In Microbial Cell Factories By Data Mining, Flux Modeling, And Metabolic Engineering, Gang Wu
McKelvey School of Engineering Graduate Student Theses & Dissertations
The long-held assumption of never-ending rapid growth in biotechnology and especially in synthetic biology has been recently questioned, due to lack of substantial return of investment. One of the main reasons for failures in synthetic biology and metabolic engineering is the metabolic burdens that result in resource losses. Metabolic burden is defined as the portion of a host cells resources either energy molecules (e.g., NADH, NADPH and ATP) or carbon building blocks (e.g., amino acids) that is used to maintain the engineered components (e.g., pathways). As a result, the effectiveness of synthetic biology tools heavily dependents on cell capability to …
Goggle Augmented Imaging And Navigation System For Fluorescence-Guided Surgery, Suman Bikash Mondal
Goggle Augmented Imaging And Navigation System For Fluorescence-Guided Surgery, Suman Bikash Mondal
McKelvey School of Engineering Graduate Student Theses & Dissertations
Surgery remains the only curative option for most solid tumors. The standard-of-care usually involves tumor resection and sentinel lymph node biopsy for cancer staging. Surgeons rely on their vision and touch to distinguish healthy from cancer tissue during surgery, often leading to incomplete tumor resection that necessitates repeat surgery. Sentinel lymph node biopsy by conventional radioactive tracking exposes patients and caregivers to ionizing radiation, while blue dye tracking stains the tissue highlighting only superficial lymph nodes. Improper identification of sentinel lymph nodes may misdiagnose the stage of the cancer. Therefore there is a clinical need for accurate intraoperative tumor and …
Theory Of Carrier Transport From First Principles: Applications In Photovoltaic And Thermoelectric Materials, Alireza Faghaninia
Theory Of Carrier Transport From First Principles: Applications In Photovoltaic And Thermoelectric Materials, Alireza Faghaninia
McKelvey School of Engineering Graduate Student Theses & Dissertations
New sources of energy that are environmentally friendly, cost-effective, and renewable are essential if we are to combat the effects of global climate change. Two of these sources are solar photovoltaic (PV) cells to convert sunlight into electricity and thermoelectric (TE) devices to convert heat to electricity. To be practical on a large scale, the properties (e.g. electrical conductivity, band gap, Seebeck coefficient, etc) of the the underlying materials must be improved significantly through judicious control of structure and composition. Significant understanding of materials properties is required to design and engineer new high-performing materials. First principles calculations using density functional …
Feed-Forward Inhibitory Circuits In Hippocampus And Their Computational Role In Fragile X Syndrome, Sarah Lauren Wahlstrom Helgren
Feed-Forward Inhibitory Circuits In Hippocampus And Their Computational Role In Fragile X Syndrome, Sarah Lauren Wahlstrom Helgren
McKelvey School of Engineering Graduate Student Theses & Dissertations
Feed-forward inhibitory (FFI) circuits are canonical neural microcircuits. They are unique in that they are comprised of excitation rapidly followed by a time-locked inhibition. This sequence provides for a powerful computational tool, but also a challenge in the analysis and study of these circuits. In this work, mechanisms and computations of two hippocampal FFI circuits have been examined. Specifically, the modulation of synaptic strength of the excitation and the inhibition is studied during constant-frequency and naturalistic stimulus patterns to reveal how FFI circuit properties and operations are dynamically modulated during ongoing activity. In the first part, the FFI circuit dysfunction …
Improving Radiation Therapy Through Motion Tracking, Hanlin Wan
Improving Radiation Therapy Through Motion Tracking, Hanlin Wan
McKelvey School of Engineering Graduate Student Theses & Dissertations
Radiation therapy is a widely-used cancer treatment method in which lethal doses of ionizing radiation are delivered to cancerous cells. Given the high dose requirements and the risk of associated complications, it is essential that radiation be targeted to cancerous cells while minimizing the dose to surrounding tissue. While current technology allows for accurate targeting of radiation dose, there is one major hurdle: Respiratory motion causes movement of up to a few centimeters of tumors in the abdomen and thorax, rendering even the most accurate radiation delivery machine highly inaccurate. Imaging devices integrated with the treatment machines allow us to …
Environmental Fullerene Chemistry: Elucidating Critical Reaction Pathways And Resulting Products In The Aqueous Phase, Jiewei Wu
McKelvey School of Engineering Graduate Student Theses & Dissertations
As the production of fullerenes and fullerene-based materials approaches industrial scale, there are increasing interests/concerns regarding their (potential) environmental impact(s) upon release. To date, a number of critical, aqueous-based fullerene transformation pathways under environmentally relevant conditions remain poorly understood. Comprehensive, fundamental, and quantitative understanding of the potential (major) reaction pathways and resulting products of fullerene materials, particularly in aquatic systems, is now crucial for their accurate fate, transport, life cycle, risk assessment(s), and thus ultimate material sustainability.
Herein, this dissertation is focused on identifying and elucidating aqueous transformation pathways of fullerene materials, focused on C60 as a model fullerene, under …
Visualization Of Deep Convolutional Neural Networks, Dingwen Li
Visualization Of Deep Convolutional Neural Networks, Dingwen Li
McKelvey School of Engineering Graduate Student Theses & Dissertations
Deep learning has achieved great accuracy in large scale image classification and scene recognition tasks, especially after the Convolutional Neural Network (CNN) model was introduced. Although a CNN often demonstrates very good classification results, it is usually unclear how or why a classification result is achieved. The objective of this thesis is to explore several existing visualization approaches which offer intuitive visual results. The thesis focuses on three visualization approaches: (1) image masking which highlights the region of image with high influence on the classification, (2) Taylor decomposition back-propagation which generates a per pixel heat map that describes each pixel's …
Lesion Identification And The Effect Of Lesion On Motor Mapping After Stroke, Ruixi Zhou
Lesion Identification And The Effect Of Lesion On Motor Mapping After Stroke, Ruixi Zhou
McKelvey School of Engineering Graduate Student Theses & Dissertations
Stroke is the most common cause of long-term severe disability and the motor system that is most commonly affected in stroke. One of the mechanisms that underlies recovery of motor deficits is reorganization or remapping of functional representations around the motor cortex. This mechanism has been shown in monkeys, but results in human subjects have been variable. In this thesis, I used a database that includes longitudinal behavioral and multimodal imaging data in both stroke patients and healthy controls for two research projects. Firstly, I improved an automatic lesion segmentation method to aid in the identification of the location and …
Acoustic Firearm Discharge Detection And Classification In An Enclosed Environment, Lorenzo Luzi, Eric Gonzalez, Paul Bruillard, Matthew Prowant, James Skorpik, Michael Hughes, Scott Child, Duane Kist, John E. Mccarthy
Acoustic Firearm Discharge Detection And Classification In An Enclosed Environment, Lorenzo Luzi, Eric Gonzalez, Paul Bruillard, Matthew Prowant, James Skorpik, Michael Hughes, Scott Child, Duane Kist, John E. Mccarthy
Mathematics Faculty Research
Two different signal processing algorithms are described for detection and classification of acoustic signals generated by firearm discharges in small enclosed spaces. The first is based on the logarithm of the signal energy. The second is a joint entropy. The current study indicates that a system using both signal energy and joint entropy would be able to both detect weapon discharges and classify weapon type, in small spaces, with high statistical certainty.
Grafalgo - A Library Of Graph Algorithms And Supporting Data Structures (Revised), Jonathan Turner
Grafalgo - A Library Of Graph Algorithms And Supporting Data Structures (Revised), Jonathan Turner
All Computer Science and Engineering Research
This report provides an (updated) 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.
The Effects Of Rarefaction And Thermal Non-Equilibrium On A Blunt Body And A Bicone In Hypersonic Flow And Their Shape Optimization For Reducing Both Drag And Heat Transfer, Samuel Gardner
McKelvey School of Engineering Graduate Student Theses & Dissertations
Design of space vehicles pose many challenging problems due to their hypersonic speeds since they need to travel through different flow regimes due to changes in the density of the atmosphere with altitude. Some of the key characteristics associated with hypersonic flow are extremely high temperatures and heat transfer to the wall of the spacecraft. At these temperatures, the assumption of thermal equilibrium is no longer valid and the effect of rotational non-equilibrium must be included in the modeling of diatomic gas flow. This thesis employs the Navier-Stokes equations, which are modified to include a rotational non-equilibrium relaxation model to …
Locality-Aware Dynamic Task Graph Scheduling, Jordyn Maglalang, Sriram Krishnamoorthy, Kunal Agrawal
Locality-Aware Dynamic Task Graph Scheduling, Jordyn Maglalang, Sriram Krishnamoorthy, Kunal Agrawal
All Computer Science and Engineering Research
Dynamic task graph schedulers automatically balance work across processor cores by scheduling tasks among available threads while preserving dependences. In this paper, we design NabbitC, a provably efficient dynamic task graph scheduler that accounts for data locality on NUMA systems. NabbitC allows users to assign a color to each task representing the location (e.g., a processor core) that has the most efficient access to data needed during that node’s execution. NabbitC then automatically adjusts the scheduling so as to preferentially execute each node at the location that matches its color—leading to better locality because the node is likely to make …
The Next Generation Of Wireless Cyber-Physical Simulator, Xinghan Wang, Kevin Xu
The Next Generation Of Wireless Cyber-Physical Simulator, Xinghan Wang, Kevin Xu
Undergraduate Research Symposium Posters
In order to make Wireless Cyber-Physical Simulator(WCPS) more accessible to people in the research community, and also to improve its accuracy of representing real industrial models, we worked on the dockerization of WCPS, and implemented the multi-rate feature for WCPS, enabling the simulator to have different network rate and plant rate when running a simulation. We created a new version of WCPS by dockerizing run-time libraries and the TOSSIM server and also embedding the multi-rate feature in the old version. This report includes the introduction and dockerization of WCPS, and shows the results of using the new generation of WCPS …
Segmentation And Strain Mapping Of A Beating Heart, Kenna Middleton
Segmentation And Strain Mapping Of A Beating Heart, Kenna Middleton
McKelvey School of Engineering Graduate Student Theses & Dissertations
Conventional methods of estimating deformation optically often compare image intensities before and after deformation to help estimate the strain fields. However, these current meth ods often introduce undesirable error that propagates through the system, growing larger through each strain calculation. These errors create false, concentrated regions of strain throughout the image. Additionally, gathering and evaluating images in three- and four dimensional space creates even more difficulty for conventional methods. Here, by imple menting new techniques of gathering four-dimensional ultrasound data sets and calculating deformation fields with traditional errors reduced three-fold, four-dimensional images were evaluated to create a novel visualization tool …
Measurement, Modeling, And Mitigation Of Lead Impacts From General Aviation, Stephen Neil Feinberg
Measurement, Modeling, And Mitigation Of Lead Impacts From General Aviation, Stephen Neil Feinberg
McKelvey School of Engineering Graduate Student Theses & Dissertations
Airborne lead (Pb) has been regulated as a criteria pollutant by the United States Environmental Protection Agency (EPA) since the Clean Air Act and its amendments in the 1970s. During the 1970s, atmospheric Pb emissions were dominated by the combustion of leaded automobile fuel and metals manufacturing. Over time, those emissions have decreased greatly and according to the EPA the largest emitter of Pb today is piston-engine aircraft. Additionally, in 2008 the EPA reduced the National Ambient Air Quality Standard (NAAQS) for Pb by an order of magnitude. These combined factors served as the impetus for further study of general …
Understanding The Nano- And Macroscale Processes Impacting Arsenic Mobilization During Managed Aquifer Recharge Using Reclaimed Wastewater, Chelsea Wren Neil
Understanding The Nano- And Macroscale Processes Impacting Arsenic Mobilization During Managed Aquifer Recharge Using Reclaimed Wastewater, Chelsea Wren Neil
McKelvey School of Engineering Graduate Student Theses & Dissertations
Managed aquifer recharge (MAR) utilizing reclaimed wastewater is a vital means of replenishing natural freshwater supplies in order to meet growing demands. Unfortunately, this process has been found to induce unfavorable geochemical reactions which mobilize arsenic from aquifer sediments. This process is further complicated by the simultaneous formation of iron(III) (hydr)oxide secondary minerals, which can sorb aqueous arsenic. It is crucial to fully elucidate these physico-chemical processes in order to establish safe MAR operations which minimize arsenic release. Thus, the mechanisms controlling arsenic release from arsenopyrite during MAR were investigated from the nano- to macroscale.
First, nanoscale iron(III) (hydr)oxide nucleation …
Clinical Application Of Electrocardiographic Imaging In Patients With Ischemic Cardiomyopathy, Early Repolarization Syndrome And Brugada Syndrome, Junjie Zhang
McKelvey School of Engineering Graduate Student Theses & Dissertations
Electrocardiographic Imaging (ECGI) is a noninvasive modality for human application in both research and clinical settings. It is an important tool for investigation of abnormal electrophysiological (EP) substrates and arrhythmias in patients. Multi-channel body surface potential recordings and the patient-specific heart-torso geometry from ECG gated computed tomography are processed by ECGI algorithms to reconstruct epicardial potentials, electrograms and patterns of activation and repolarization. ECGI is able to continuously generate high-resolution, panoramic EP maps of the entire heart on a beat-by-beat basis, which cannot be achieved with invasive catheter mapping.
ECGI was applied in ischemic cardiomyopathy patients to characterize the abnormal …
Thermally Evolved & Separated Composition Of Atmospheric Aerosols: Development And Application Of Advanced Data Analysis Techniques For A Thermal Desorption Aerosol Gas Chromatograph (Tag), Yaping Zhang
McKelvey School of Engineering Graduate Student Theses & Dissertations
Atmospheric organic aerosols are composed of thousands of individual compounds, interacting with climate through changes in aerosol optical properties and cloud interactions, and can be detrimental to human health. Aerosol mass spectrometry (MS) and gas chromatography (GC)-separated MS measurements have been utilized to better characterize the chemical composition of this material that comes from a variety of sources and experiences continuous oxidation while in the atmosphere. This dissertation describes the development of a novel rapid data analysis method for grouping of major components within chromatography-separated measurements and first application using thermal desorption aerosol gas chromatograph (TAG) – MS data. Chromatograms …
Molecularly Targeted Nanoparticles For Modulation Of Inflammatory Mediators In Atherosclerosis, Rohun Udatta Palekar
Molecularly Targeted Nanoparticles For Modulation Of Inflammatory Mediators In Atherosclerosis, Rohun Udatta Palekar
McKelvey School of Engineering Graduate Student Theses & Dissertations
The enzyme thrombin has been demonstrated through experimental and clinical studies to play a crucial role in mediating both inflammation and thrombosis in atherosclerosis. The cellular effects of thrombin in promoting atherosclerosis involve the activation of signaling pathways that result in the secretion of a host of various chemokines, cytokines, cell adhesion molecules, etc. that promote vascular inflammation. Due in part to thrombin and other pro-atherogenic molecules, this prolonged inflammatory state in atherosclerosis results in the deterioration of the endothelium, increasing the risk of focal thrombosis. Current treatment strategies to address the role of thrombin in atherosclerosis, despite efficacy of …
Novel Applications Of Electrostatic Precipitators In Coal - Biomass Combustion Systems, He Jing
Novel Applications Of Electrostatic Precipitators In Coal - Biomass Combustion Systems, He Jing
McKelvey School of Engineering Graduate Student Theses & Dissertations
Pulverized coal combustion is an important source of electricity production worldwide. However, it is also a primary air pollution emission (particulate matters, mercury, etc.) source. Electrostatic precipitators (ESPs) are widely used in coal-fired power plants to control particulate matters. This dissertation contributes in the study of the pollution formation from coal combustion processes and pollution control based on ESPs in the following three aspects: (1) explore novel applications of ESPs in particulate matters and mercury removal; (2) develop and evaluate an compact electrostatic precipitator for sampling purpose, which can support offline fly ash particle analysis; (3) study the submicrometer particle …
Relating Neural Dynamics To Olfactory Coding And Behavior, Chao Li
Relating Neural Dynamics To Olfactory Coding And Behavior, Chao Li
McKelvey School of Engineering Graduate Student Theses & Dissertations
Sensory stimuli often evoke temporal patterns of spiking activity across a population of neurons in the early processing stages. What features of these spatiotemporal responses encode behaviorally relevant information, and how dynamic processing of sensory signals facilitates information processing are fundamental problems in sensory neuroscience that remain to be understood. In this thesis, I have investigated these issues using a relatively simple invertebrate model (locusts; Schistocerca americana).
In locusts, odorants are transduced into electrical signals by olfactory sensory neurons in the antenna and are subsequently relayed to the downstream neural circuit in the antennal lobe (analogous to the olfactory bulb …
Copper And Zinc Oxide Composite Nanostructures For Solar Energy Harvesting, Fei Wu
Copper And Zinc Oxide Composite Nanostructures For Solar Energy Harvesting, Fei Wu
McKelvey School of Engineering Graduate Student Theses & Dissertations
Solar energy is a clean and sustainable energy source to counter global environmental issues of rising atmospheric CO2 levels and depletion of natural resources. To extract useful work from solar energy, silicon-based photovoltaic devices are extensively used. The technological maturity and the high quality of silicon (Si) make it a material of choice. However limitations in Si exist, ranging from its indirect band gap to low light absorption coefficient and energy and capital intensive crystal growth schemes. Therefore, alternate materials that are earth-abundant, benign and simpler to process are needed for developing new platforms for solar energy harvesting applications.
In …
Data Structures And Algorithms For Scalable Ndn Forwarding, Haowei Yuan
Data Structures And Algorithms For Scalable Ndn Forwarding, Haowei Yuan
McKelvey School of Engineering Graduate Student Theses & Dissertations
Named Data Networking (NDN) is a recently proposed general-purpose network architecture that aims to address the limitations of the Internet Protocol (IP), while maintaining its strengths. NDN takes an information-centric approach, focusing on named data rather than computer addresses. In NDN, the content is identified by its name, and each NDN packet has a name that specifies the content it is fetching or delivering. Since there are no source and destination addresses in an NDN packet, it is forwarded based on a lookup of its name in the forwarding plane, which consists of the Forwarding Information Base (FIB), Pending Interest …
Applying Bayesian Machine Learning Methods To Theoretical Surface Science, Shane Carr
Applying Bayesian Machine Learning Methods To Theoretical Surface Science, Shane Carr
McKelvey School of Engineering Graduate Student Theses & Dissertations
Machine learning is a rapidly evolving field in computer science with increasingly many applications to other domains. In this thesis, I present a Bayesian machine learning approach to solving a problem in theoretical surface science: calculating the preferred active site on a catalyst surface for a given adsorbate molecule. I formulate the problem as a low-dimensional objective function. I show how the objective function can be approximated into a certain confidence interval using just one iteration of the self-consistent field (SCF) loop in density functional theory (DFT). I then use Bayesian optimization to perform a global search for the solution. …
Optimization Of Looped Airfoil Wind Turbine (Lawt) And Looped Airfoil Hydro-Turbine (Laht) Design Parameters For Maximum Power Generation, Binhe Song
McKelvey School of Engineering Graduate Student Theses & Dissertations
This focus of this research is on the study of the aerodynamic performance of a Looped Airfoil Wind Turbine (LAWT™) using the Computational Fluid Dynamics (CFD) software. The looped airfoil wind turbine (LAWT™) is a patented new technology by EverLift Wind Technology, Inc. for generating power from wind. It takes advantage of the superior lift force of a linearly traveling wing compared to the rotating blades in conventional wind turbine configurations. Compared to horizontal and vertical axis wind turbines, the LAWT™ can be manufactured with minimal cost because it does not require complex gear systems and its blades have a …
Cyber-Physical Co-Design Of Wireless Control Systems, Bo Li
Cyber-Physical Co-Design Of Wireless Control Systems, Bo Li
McKelvey School of Engineering Graduate Student Theses & Dissertations
Wireless sensor-actuator network (WSAN) technology is gaining rapid adoption in process industries because of its advantages in lowering deployment and maintenance cost in challenging environments. While early success of industrial WSANs has been recognized, significant potential remains in exploring WSANs as unified networks for industrial plants.
This thesis research explores a cyber-physical co-design approach to design wireless control systems. To enable holistic studies of wireless control systems, we have developed the Wireless Cyber-Physical Simulator (WCPS), an integrated co-simulation environment that integrates Simulink and our implementation of WSANs based on the industrial WirelessHART standard. We further develop novel WSAN protocols tailored …
Automating Intensity Modulated Radiation Therapy Treatment Planning By Using Hierarchical Optimization, Paras Babu Tiwari
Automating Intensity Modulated Radiation Therapy Treatment Planning By Using Hierarchical Optimization, Paras Babu Tiwari
McKelvey School of Engineering Graduate Student Theses & Dissertations
The intensity modulated radiation therapy (IMRT) optimizes the beam’s intensity to deliver the prescribed dose to the target while minimizing the radiation exposure to normal structures. The IMRT optimization is a complex optimization problem because of the multiple conflicting objectives in it. Due to the complexity of the optimization, the IMRT treatment planning is still a trial and error process. Hierarchical optimization was proposed to automate the treatment planning process, but its potential has not been demonstrated in a clinical setting. Moreover, hierarchical optimization is slower than the traditional optimization. The dissertation studied a sampling algorithm to reduce the hierarchical …
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.