Graph Theory for Computer Science (eBook)

Manikandan Rajagopal, Ramkumar Sivasakthivel, Joseph Varghese Kureethara, Niranjanamurthy M., Biswadip Basu Mallik (Herausgeber)

eBook Download: EPUB

2025
793 Seiten
Wiley-Scrivener (Verlag)
978-1-394-30260-4 (ISBN)

Infos

This book is a vital resource for anyone looking to understand the essential role of graph theory as the unifying thread that connects and provides innovative solutions across a wide spectrum of modern computer science disciplines.

Graph theory is a traditional mathematical discipline that has evolved as a basic tool for modeling and analyzing the complex relationships between different technological landscapes. Graph theory helps explain the semantic and syntactic relationships in natural language processing, a technology behind many businesses. Disciplinary and industry developments are seeing a major transition towards more interconnected and data-driven decision-making, and the application of graph theory will facilitate this transition. Disciplines such as parallel and distributive computing will gain insights into how graph theory can help with resource optimization and job scheduling, creating considerable change in the design and development of scalable systems. This book provides comprehensive coverage of how graph theory acts as the thread that connects different areas of computer science to create innovative solutions to modern technological problems. Using a multi-faceted approach, the book explores the fundamentals and role of graph theory in molding complex computational processes across a wide spectrum of computer science.

Manikandan Rajagopal, PhD is an Associate Professor at Christ University with more than a decade of research experience. He has published three textbooks, more than ten book chapters, and 15 journal articles in reputed journals and conferences. His areas of interest include data mining, optimization techniques, semantic mining, and intelligent agents.

Ramkumar Sivasakthivel, PhD is an Associate Professor at Christ University with more than 12 years of experience. He has published four textbooks, several papers in international journals and conferences, and has been granted two patents. His fields of interest are biosignal processing, artificial intelligence, human-computer interface, brain-computer interface, and machine vision.

Joseph Varghese Kureethara, PhD is a Professor of Mathematics at Christ University with more than 17 years of experience in research and teaching. He has published more than 230 articles in international journals and conferences, co-edited five books, and authored six books. He has also delivered invited talks at over fifty conferences and workshops and serves as a member of several institutions' boards.

Niranjanamurthy M., PhD is an Assistant Professor in the Department of Artificial Intelligence and Machine Learning at the BMS Institute of Technology and Management with more than 13 years of experience. He has published more than 95 articles in various national and international journals and conferences and filed 30 patents. His areas of interest are data science, machine learning, e-commerce, software testing, and software engineering.

Biswadip Basu Mallik, PhD is an Associate Professor of Mathematics in the Department of Basic Sciences and Humanities at the Institute of Engineering and Management with more than 22 years of experience. He has published five textbooks, thirteen edited books, five patents, and several research papers and book chapters in various scientific journals. His fields of research work include computational fluid dynamics, mathematical modelling, machine learning, and optimization.

Textauszug

1
A Comprehensive Study on Pathfinding in Dynamic Graphs Using Automaton and Two-Way Depth-First Search

Ajayaditya L.1 and Anitha N.2*

1Department of Mechatronics, Kumaraguru College of Technology, Coimbatore, India

2Department of Mathematics, Kumaraguru College of Technology, Coimbatore, India

Abstract

Efficient pathfinding in time-varying directed acyclic graphs is crucial for numerous applications, necessitating incremental updates and maintenance of connectivity. This paper presents a formal automata-theoretic approach combining graph automata, graph transducers, and two-way search techniques. Graph automata model the dynamic acyclic graph evolution, transitioning between configurations. Graph transducers apply transformation rules to handle dynamic changes such as node and edge additions, removals, and property modifications. Two-way breadth-first and depth-first searches augmented with graph walking automata explore the dynamic acyclic graphs, computing potential paths and reconnecting affected routes. Incremental path update algorithms identify impacted regions, apply transducer rules, and reconnect paths via localized two-way searches. Path optimization strategies further enhance efficiency. Comprehensive mathematical formulations, algorithms, and complexity analyses demonstrate the approach’s rigor and applicability to resilient pathfinding in evolving dynamic acyclic graphs.

Keywords: Directed acyclic graphs (DAGs), dynamic graphs, incremental pathfinding, graph automata, graph transducers, two-way search, graph walking automata

1.1 Introduction

Directed acyclic graphs (DAGs) are a type of directed graph with no cycles, meaning that there are no paths that start and end at the same vertex while traversing the same set of edges. DAGs have numerous applications in fields such as task scheduling, data processing pipelines, and network routing. In many real-world scenarios, these DAGs are not static but rather evolve over time, with vertices (nodes) and edges being added, removed, or modified. We refer to such structures as time-varying or dynamic DAGs.

Efficiently finding and maintaining paths in these dynamic DAGs is a critical problem with applications in areas like network routing, where the network topology may change due to link failures or additions, necessitating the recomputation or update of existing paths. Traditional pathfinding algorithms like Dijkstra’s or breadth-first search (BFS) can be employed to compute paths from scratch after each change, but this approach can be computationally expensive, especially for large graphs or frequent changes.

In this paper, we present a formal automata-theoretic approach that combines graph automata, graph transducers, and two-way search techniques to enable efficient incremental pathfinding in time-varying DAGs. Our approach aims to update and maintain existing paths in response to dynamic changes, rather than recomputing them from scratch, thereby reducing computational overhead and improving overall efficiency.

1.1.1 Literature Review

The problem of finding and maintaining paths in dynamic graphs has been extensively studied in various domains, including computer networks, transportation systems, and task scheduling. Several approaches have been proposed to address this challenge, ranging from classical algorithms to more sophisticated techniques involving automata theory and formal methods.

Conventional pathfinding techniques, like BFS [2] and Dijkstra’s algorithm [1], are typically utilized for recalculating paths whenever there is a modification in the graph’s configuration. However, these approaches can be computationally expensive, especially for large graphs or scenarios with frequent dynamic changes [3].

To address this limitation, incremental pathfinding algorithms have been developed, which aim to update and maintain existing paths more efficiently by exploiting the structural properties of the graph and the locality of changes. King’s algorithm [4] and its variants [5, 6] are notable examples of incremental pathfinding techniques for dynamic graphs.

In recent years, researchers have explored the use of automata theory and formal methods for modeling and reasoning about dynamic graph structures. Graph automata [7, 8] and graph transducers [9, 10] have emerged as powerful tools for representing and transforming graph structures, respectively.

Eppstein et al. [11] introduced the concept of incremental graph automata, which can efficiently update their state in response to dynamic changes in the graph. This work laid the foundation for subsequent research on automata-based approaches to incremental pathfinding.

Approaches based on graph grammars and graph transformation systems have also been proposed for modeling and analyzing dynamic graphs [12, 13].

These techniques allow for the specification of graph rewriting rules and the implication of transformations to update the graph.

The concept of two-way search, which involves exploring the graph from both the source and target vertices simultaneously, has been employed to improve the efficiency of pathfinding algorithms [14, 15]. Bidirectional search techniques have been shown to be particularly effective for dynamic graphs, as they can leverage previously computed paths and reconnect them after changes in the graph structure [16, 17].

In the domain of network routing, techniques such as the Routing Information Protocol [18] and the Open Shortest Path First protocol [19] have been developed to handle dynamic changes in network topologies. These protocols utilize incremental updates and dissemination of routing information to efficiently maintain paths and routing tables.

While the above-mentioned works have made significant contributions to the field of dynamic graph pathfinding, the integration of automatatheoretic concepts, graph transducers, and two-way search techniques has received limited attention. Our proposed approach aims to combine these formal methods to enable efficient incremental pathfinding in time-varying DAGs.

1.2 Preliminaries

1.2.1 Directed Acyclic Graphs (DAGs)

A DAG G = (V, E, Σ, λ) is a labeled directed graph, where

• V: the set of vertices (nodes),
• E ⊆ V × V: the set of directed edges,

  Figure 1.1 Directed acyclic graph.

• Σ: the set of vertex labels, and
• λ: V → Σ is the vertex labeling function, assigning labels to vertices.

A DAG contains directed edges with no cycles, meaning that there are no paths that start and end at the same vertex while traversing the same set of edges. Formally, a DAG satisfies the following condition:

where E+ represents the transitive closure of the edge relation 5, representing all possible paths present in the given graph G.

Figure 1.1 illustrates an example of a DAG with labeled vertices. In this graph, there are no paths that start and end at the same vertex, ensuring the acyclicity property. DAGs have numerous applications in fields such as task scheduling, data processing pipelines, and network routing, where the absence of cycles is a desirable property.

In many real-world scenarios, DAGs are not static but rather evolve over time, with vertices and edges being added, removed, or modified. We refer to such structures as time-varying or dynamic DAGs. Efficiently finding and maintaining paths in these dynamic DAGs is a critical problem with applications in areas like network routing, where the network topology may change due to link failures or additions, necessitating the recomputation or update of existing paths.

1.2.2 Dynamic Graphs

A dynamic graph G′ = (Gt)t∈

• Erscheint lt. Verlag: 6.11.2025
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Schlagworte: Artificial Neural Networks • Automata Theory • Big Data Analytics • Bioinformatics • Blockchain technology • Computer Science • computer vision • cryptography • Fuzzy Logic • graph theory • Image Processing • Natural Language Processing • Parallel and distributed • Quantum Computing • theory of computing
• ISBN-10: 1-394-30260-6 / 1394302606
• ISBN-13: 978-1-394-30260-4 / 9781394302604