MS, Kent State University, 2025, College of Arts and Sciences / Department of Computer Science

Given an undirected, weighted, and labeled data graph 𝐺, a source node 𝑠, a desti- nation node 𝑡, and an ordered sequence of query keywords, a Keyword-Constrained Shortest Path (KCSP) query retrieves the shortest path that passes some vertices with query keywords in order. Existing methods for processing such queries have limita- tions: (i) they fail to handle arbitrary keyword constraints efficiently; and (ii) they rely heavily on exhaustive search techniques that are computationally expensive. Inspired by these challenges, we propose a learning-based framework for efficient processing of KCSP queries. A pre-processing step offline builds indexes and pre-trains learning- based models to accelerate online KCSP query performance. Our proposed approach integrates path pruning and neural network-based prediction to reduce computational cost, eliminates the need for exhaustive traversal, and allows efficient query processing in large-scale graphs by combining machine learning with graph algorithm optimiza- tions. Extensive experiments have been conducted to evaluate our proposed KCSP approach over both Oldenburg and Synthetic graphs, in terms of the query efficiency and scalabili

Committee: Xiang Lian Dr (Advisor); Gokarna Sharma Dr (Committee Member); Ruoming Jin Dr (Committee Member) Subjects: Computer Science

BA, Oberlin College, 2017, Mathematics

We study a novel model of random graph which exhibits the structural characteristics of the Watts- Strogatz small-world network. The small-world network is characterized by a high level of local clustering while also having a relatively small graph diameter. The same behavior that makes the Watts-Strogatz model behave like this also makes it difficult to analyze. Our model addresses this issue, closely mimicking the same structure experimentally while following a constructive process that makes it easier to analyze mathematically. We present a bound on the average shortest path length in our new model, which we approach by looking at the two key geometric components.

Committee: Elizabeth L. Wilmer (Advisor) Subjects: Mathematics

MS, Kent State University, 2017, College of Arts and Sciences / Department of Computer Science

The Minimum Eccentricity Shortest Path (MESP) Problem consists of determining a shortest path (a path of minimum length between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert who described a linear time approximation algorithm for the problem. A minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line. MESP-problem is NP-hard on general graphs, but it can be solved in linear time for trees. In this thesis, we implement this approximation algorithm for MESP and the algorithm that uses a small eccentricity shortest path found to perform a graph linearization. We analyze their performances on synthetic (generated) graphs, such as interval graphs and proper interval graphs and on real-world networks, such as Gene-to-Gene Networks (GGI), Protein-to-Protein Networks (PPI), Yeast Network, US Air Transportation, the Internet at the Autonomous System, and World-Wide-Web. We have observed that embedding into the line gives a good approximation for the bandwidth problem in terms of maximum and average bandwidth. Moreover, we revealed that the length of a shortest path obtained by the MESP algorithm impacts the maximum and average bandwidth. Additionally, regarding synthetic graphs, we have seen that maximum bandwidth and average bandwidth calculated from embedding into the line increase or decrease according to the change in length of intervals in proper interval graphs and degree sequence in interval graphs. Also, we have noticed that the embedding of proper interval graphs into the line resembles a proper interval ordering of its vertices known from the literature.

Committee: Dragan Feodor (Advisor); Peyravi Hassan (Committee Member); Sharma Gokarna (Committee Member) Subjects: Computer Science

Doctor of Philosophy, University of Toledo, 2014, Geography

Optimizing the supply chain has been increasingly important for the success of both manufacturers and retailers. This optimization has reduced costs for companies that are involved in the transport process and reduced cost to the end consumers, which brings benefits to both sides of the profit chain. Under difficult economic conditions, such as high fuel prices, mass congestion on major highway corridors, and strict reliability requirements for specific commodity types, the tangible as well as the intangible costs of freight transportation has been increasing rapidly. It swallows profits from the industry, increasing the cost for customers. Intermodal freight transportation has been introduced in recent years and has been more frequently selected by logistics companies, third-party logistics companies, and manufacturers to optimize the whole freight transport process. The trend of using more intermodal freight transportation is discussed in a qualitative perspective in the first part of this dissertation. Then the dissertation introduces a new shortest path algorithm entitled Tree Spanning Method (TSM) for large network processing. The new TSM algorithm is used as the main route planning algorithm throughout the dissertation for software development as well as freight demand forecasting. Due to the lack of specialized intermodal freight planning software in the industry, this dissertation discusses the key techniques in creating a specialized freight planning software, and a beta version of the software entitled "RouteInfo" is developed and introduced. The software works in a fashion similar to the Spatial Decision Support System. It enables users to be fully involved in the decision-making process and is able to determine the least expensive path between origins and designations on an integrated intermodal network. Real data includes USA highways and Canadian highways, and rail and maritime networks are integrated into the graphical user interface. Freight (open full item for complete abstract)

Committee: Peter Lindquist Ph.D. (Committee Chair); Daniel Hammel Ph.D. (Committee Member); Eddie Yein Juin Chou P.E. (Committee Member); Neil Reid Ph.D. (Committee Member); Yue Zhang Ph.D. (Committee Member) Subjects: Geographic Information Science; Transportation; Transportation Planning

PhD, University of Cincinnati, 2007, Engineering : Computer Science and Engineering

In this thesis we develop a framework for studying and understanding the tradeoffs involved in efficient multicast route determination. Using this framework, we developed an algorithm (Myriad) that exhibits superior theoretical and empirical results over previously published work. We have validated this work through extensive simulation using a variety of metric spaces, and by proving a series of mathematical theorems concerning degree-bounded spanning trees over metric spaces. This study is done through examination of the degree-constrained minimum average-latency spanning tree problem (or DC-MAL). Creating a solution which places each participant at their optimal locality along a path from the root is an NP-hard problem, thus motivating a search for approximate solutions. This type of organization for information relaying is a natural model of the multicast problem and lends itself to theoretical analysis that can be applied in application level peer-to-peer overlay networks. Out-degree constraints follow directly from the need for high bandwidth multimedia streams and the ability to relay the information without any loss. Study of this problem is important since it is expected that the demand for multicast applications will continue to grow, and such applications require scalability to millions of simultaneous subscribers.

Committee: Dr. Fred Annexstein (Advisor) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2010, Business Administration

I study the shortest path - capacitated maximum covering problem (SP-CMCLP). Current, ReVelle and Cohon (1985) first studied the un-capacitated version of this problem. The two objectives of the problem are the minimization of the path length from a predetermined starting node to a predetermined terminal node and the maximization of the total demand covered by the facilities located at the nodes in the path. They solved a special case in which a demand can be covered only if it is located on the path. I solve the general model. I also introduce facility capacity constraints, new algorithms and new demand coverage structures to this problem. I decompose the problem into a k-shortest path problem (kSP) and a capacitated maximum covering problem (CMCLP). The k-shortest path problem is solved by a path deletion algorithm. The capacitated maximum covering problem is solved by various heuristics and meta-heuristics including lagrangian relaxation, two versions of Tabu search and a simulated annealing method. To the knowledge of the author, the Tabu search and simulated annealing methods introduced are the first meta-heuristics developed for the capacitated maximum covering problem. In these meta-heuristics, I use four neighborhood structures. These are 1) one-interchange which exchanges an selected facility with an unselected facility, 2) client shift which shifts a satisfied demand from one selected facility to another selected facility, 3) demand swap (or demand reallocation) which swaps one (or more) assigned demand node (nodes) with one (or more) unassigned demand node (nodes) within the coverage distance of a selected facility site, 4) demand addition which adds one or more unassigned demand to a selected facility. I design an embedded meta-heuristic procedure which has inner loops of single neighborhoods and an outer loop of multiple alternate inner loops. I design a heuristic method and a penalty method for the demand allocation sub-problem in the embedded Tabu s (open full item for complete abstract)

Committee: John R. Current PhD (Advisor); David A. Schilling PhD (Committee Member); Keely L. Croxton PhD (Committee Member) Subjects: Management; Operations Research

Master of Computer Science, Miami University, 2008, Computer Science and Systems Analysis

We propose an extremely simple and efficient shortest path algorithm that computes an optimal shortest path between a pair of points in a metric space. Our algorithm works similarly to Dijkstra's algorithm, but uses heuristic information provided by an approximate distance oracle to prune nodes that cannot be on the shortest path. Our algorithm returns the exact shortest path in time (CS*)O(dim) using this linear size data structure, where S* is the number of vertices in the shortest path, dim is the doubling dimension of input graph, and C is a constant. We prove that this is nearly optimal by proving a lower-bound of (CS*)Ω(dim). This paper presents theoretical and experimental results to prove that if there exist efficient distance oracles for road maps, then our algorithm explores very few nodes compared to Dijkstra's algorithm, A* algorithm, and Goldberg, et al's ALT algorithms.

Committee: William Brinkman Dr. (Advisor); James Kiper Dr. (Committee Member); Lukasz Opyrchal Dr. (Committee Member) Subjects: Computer Science

PHD, Kent State University, 2012, College of Arts and Sciences / Department of Computer Science

This dissertation focuses on developing novel techniques to help understand, analyze, and query large graphs by utilizing backbone structures. Network backbone depicts a core substructure which not only offers concise and highlighted topological view of original graph, but also carries a large amount of essential information, such as information flow. In this dissertation, we introduce a novel backbone structure “gate graph” to provide a simplified topological view of original graph while preserving its distance measure. A graph simplification algorithm based on set cover framework is proposed to extract gate graph. We show theoretically and empirically that both approaches considerably reduce the complexity of original graph in terms of the number of vertices. In addition, we also examine how to efficiently answer reachability query and shortest path (distance) query on large graphs, by utilizing tailored backbone structures: 1) first, to address scalability challenge in reachability query answering on massive graphs, we extract a “reachability backbone” and then leverage it to help scale the existing reachability indexing algorithms and speed up online query processing approaches; 2) secondly, to efficiently answer distance queries on large directed graphs, we present a novel labeling scheme, referred to as Highway-Centric Labeling, utilizing a directed spanning tree as highway structure. We build an interesting connection between our labeling problem and Bipartite Set Cover problem and propose an elegant algorithm with non-trivial logarithmic bound to solve it; 3) finally, we introduce a novel Hub2-Labeling approach to compute the exact shortest path between two vertices with distance no more than 6 in large social networks. Our approach significantly extends the existing landmark approach by utilizing a large number of hubs to help estimate the distance and to help reduce the search space. We demonstrate these approaches using synthetic datasets and real-world (open full item for complete abstract)

Committee: Ruoming Jin Dr. (Advisor); Feodor Dragan Dr. (Committee Member); Jonathan Maletic Dr. (Committee Member); Robin Selinger Dr. (Committee Member); Almut Schroeder Dr. (Committee Member) Subjects: Computer Science

MS, Kent State University, 2009, College of Arts and Sciences / Department of Computer Science

There is still much research in the areas of routing and location updates in cellular communication networks. Given the limited amount of memory and power of these network devices it is desirable to find the most effective and resource conscious method for solving routing and location update problems. Recently, these problems have been addressed for simply connected cellular networks and significant results were achieved.  An effective method for addressing, location update and routing has been offered using a method of isometric embeddings into a set of three trees.  This method however does not fully work when a hole is present in the network.  To handle networks containing holes, a variation of the above method is required, where the cellular network will be decomposed into few sub-graphs that encompass the properties of the original network graph.  Proposed here is a method that will handle the above mentioned problems on cellular networks with holes, namely holes with disc structures and other shapes that have the convex property.  Also presented are two distinct methods for handling networks with multiple disc-structured holes.  These methods will also use sub-graphs to reduce the number of holes while preserving all shortest paths.

Committee: Feodor F. Dragan PhD (Advisor); Ruoming Jin PhD (Committee Member); Hassan Peyravi PhD (Committee Member) Subjects: Computer Science

Master of Science (M.S.), University of Dayton, 2011, Civil Engineering

Due to present-day significant increases in population and consequently in traffic congestion in most metropolitan cities in the world, designing of an intelligent traffic management system (ITMS) in order to detect the path with the shortest travel time is critical for emergency, health, and courier services. The aim of this thesis study was to develop a theoretical traffic detection system and capable of estimating the travel time associated with each street segment based on the traffic data updated every 20 seconds, which successively finds the path with the shortest travel time in the network by using a dynamic programming technique. Furthermore, in this study we model the travel time associated with each street segment based on the historical and real time data considering that the traffic speed on each road segment is piecewise constant. It would be useful to implement such algorithms in GIS systems such as Google map in such a way that the service delivery drivers can avoid congested routes by receiving real time traffic information.

Committee: Eustace Deogratias PhD (Committee Chair); Arthur Busch PhD, PE, PTOE (Committee Member); Maher Qumsiyeh PhD (Committee Member); Paul Goodhue PE, PTOE (Committee Member) Subjects: Civil Engineering