A Novel Edge-Efficiency-Based Algorithm for Hamiltonian Cycle and Path Detection in Graphs

A novel approach for constructing a minimum spanning tree

The spanning tree of a graph is obtained when all vertices of a graph are connected in such a way that no cycle is formed. This work proposes a new algorithm that, at each round, selects a maximal independent set of vertices (an inclusion-maximal, not necessarily maximum-cardinality, set of pairwise non-adjacent vertices) and attaches to every vertex of that set its cheapest cycle-safe incident edge to find a minimum spanning tree of any weighted graph. The procedure organizes safe-edge selections into batches indexed by maximal independent sets; its number of such batching rounds depends on the maximal independent sets selected, and this notion of a round is not directly comparable to a single iteration of Prim's or Kruskal's algorithm without further definition. Using the classical cut property, we prove that the procedure always produces a minimum spanning tree of a connected graph. If r denotes the number of independent-set rounds, a straightforward sequential implementation has worst-case running time O(r(n+m)+m log m). We do not claim, and this paper does not prove, that the number of rounds is minimized over all possible choices of maximal independent sets, nor that the resulting sequential running time improves on the classical O(m log n) bounds. This work may be useful for large weighted networks such as communication networks, wiring connections, and transportation networks.

Second shortest simple paths in directed graphs: a crossing decomposition and a span-adaptive exact algorithm

Instance-Optimality of Bidirectional Dijkstra on Simple Graphs

We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the shortest path from $s$ to $t$. We are particularly interested in instances that can be solved in sublinear time. Recently, Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan, and T\v{e}tek proved that (a version of) the bidirectional Dijkstra's algorithm is instance-optimal on positively weighted multigraphs, both directed and undirected, considering the number of vertices and edges queried by the algorithm. However, multigraphs are not the canonical setting for the shortest-path problem. The problem is typically formulated on simple graphs without loops and parallel edges. They therefore left as an open problem whether bidirectional Dijkstra remains instance-optimal on simple weighted graphs. We answer this question, but for simple graphs, the answer is more complex, depending on the setting. We show that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order. In contrast, under the order-dependent model, where incident edges have a given order, we show that bidirectional Dijkstra is not instance-optimal. For simple directed weighted graphs, we show that bidirectional Dijkstra is not instance-optimal under either the order-oblivious or the order-dependent model, being off by a factor of $\Theta(m/n)$ in both cases. We further show that no algorithm can have instance-optimality ratio $o(m/n)$ under the order-dependent model, or under the order-oblivious model when $m=O(n\sqrt{n})$. On the positive side, the above results imply that bidirectional Dijkstra is instance-optimal up to logarithmic factors on all sparse directed and undirected graphs satisfying $m/n=\log^{O(1)} n$.

On Shortest Path, BFS- and DFS-Tree Graphs

Flip graphs encode the structure of feasible transformations between combinatorial objects, making them a fundamental tool in reconfiguration problems. Tree graphs, which are flip graphs whose nodes represent the spanning trees of a graph, have received significant attention due to their algorithmic and structural properties. In this paper, we introduce new variations of tree graphs by restricting the spanning trees to shortest path trees, breadth-first search (BFS) trees, and depth-first search (DFS) trees. We prove that shortest path tree graphs are hamiltonian. Given any graph $G$, we present an algorithm that finds a hamiltonian cycle in its corresponding shortest path tree graph. We show that BFS-tree graphs and DFS-tree graphs are not necessarily connected. We establish some necessary conditions for the connectivity of BFS-tree and DFS-tree graphs. We provide an optimal linear-time algorithm for reconfiguration in shortest path tree graphs. Finally, we derive some bounds on the chromatic numbers of these new variations of tree graphs.

Finding Simple Shortest-Paths via Centroids

Centroids are used to compute an arbitrary number of simple paths with some important benefits: the expansion of a single centroid delivers an arbitrary number of paths; only a single Dijk-stra search is required to complete the task; the same algorithm can be easily coupled with heuristics that improve search efficiency.

Evaluating the Influence of Graph Density on the Efficiency of Shortest Path Algorithms Using Different Data Structures

This paper presents a comparative analysis of two variants of a classical algorithm for finding the shortest path in a connected graph. The first variant uses an adjacency matrix (AM) to verify the existence of an edge (arc) between two vertices, while the second variant performs the same verification using an adjacency list (AL). The objective of this study is to examine how graph density affects the performance of the two algorithmic modifications depending on the data structure used. A total of 95 graphs were analyzed, grouped into five sets from 100 to 500 in increments of 100. For each group, 19 graphs were generated with densities ranging from 5% to 95% in increments of 5%. The methodology includes analyzing the number of iterations, assignments, and comparisons executed by the algorithms for all graphs. The initial hypothesis assumed that the total number of operations would always be lower when using an AL instead of an adjacency matrix, regardless of graph density. The results demonstrate that this assumption is incorrect: for densities above 82%, the total number of operations is lower when using an adjacency matrix, whereas the AL is more efficient for densities below 82%, with its efficiency increasing as density decreases. These findings are particularly important for mobile technologies, as they support the design of more efficient pathfinding solutions that optimize performance and energy consumption in mobile applications.