Under the APSP conjecture, no algorithm solves the narrow core in O ( m √ n polylog( nC )) time for all polynomially bounded integer costs: the decomposition confines the known hardness of 2-SP to a small, explicitly described class of detours.
It is shown 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, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
It is proved that the classical cut property always produces a minimum spanning tree of a connected graph, and may be useful for large weighted networks such as communication networks, wiring connections, and transportation networks.
H. Bhapkar, Rezwan Ul Shaban, S. Mir et al.· Journal of the Nigerian Soci...· 0 citations
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.
The E2 Algorithm for constructing the Hamiltonian cycle in an arbitrary graph without edges’ weights is proposed and whether some general graphs are Hamiltonian is shown, to prove the correctness of the method.
Fatih Okumuş, A. Karadoğan· Fırat Üniversitesi Mühendisl...· 0 citations
Enumerating simple paths and cycles subject to a given length bound is a fundamental problem in graph algorithms. Recent algorithms, namely BC-DFS (Peng et al. 2019, 2021) and CYCLE_SEARCH (Gupta and Suzumura 2021, arXiv:2105.10094v2), employ cached barrier values to prune fruitless searches. Both algorithms turn out to produce incomplete output, and their delay-bound arguments rely on flawed claims. For CYCLE_SEARCH this is known (arXiv:2512.08392); here we establish the analogous results for BC-DFS by exhibiting graphs on which paths are missed, by identifying the defect in its barrier-update procedure, and by refuting the monotonicity claim on which its delay-bound proof rests. As our main contribution, we introduce edge-consistency, a local invariant on barrier values analogous to heuristic consistency in informed search. It provides an incremental mechanism for maintaining admissible barrier estimates and yields concise correctness proofs. We use edge-consistency as a unifying framework for design and analysis of Bounded-Scope Depth-First Search (BS-DFS) --- a new algorithm for enumerating simple paths or cycles of length at most $k$ in a directed graph. For BS-DFS we prove a worst-case delay of at most $3(k+1)(n+m)$ elementary steps between consecutive events (start, each output, termination) and an amortized delay of at most $2(k+1)(n+m)$ steps per event, the $p$-th event being reached within $2p(k+1)(n+m)$ steps; both bounds are in $O(k(n+m))$. Barrier admissibility alone is not sufficient for the delay bound: for two variants with simpler barrier management, we exhibit a graph family forcing $\Omega(k^2(n+m))$ delay between outputs. Experiments on two families of random graphs confirm our findings, support the significance of the incompleteness result, and show that achieving completeness has modest empirical cost.
Frank Bauernöppel, J. Sack· arXiv.org· 0 citations
Suppose that T is a normal spanning tree (depth-first search tree) of a graph G. If e=xy and e′=uv are edges of G, satisfying x≺Tu≺Ty≺Tv, then they are called secant edges of G with respect to T. Suppose that G has no secant edges with respect to T. If T is a path, Ghazal and Al-Mniny proved that the chromatic number is at most 3. We conjecture that there is a positive constant γ such that, for any graph G that has no secant edges with respect to a normal spanning tree T, then χ(G)≤γ. We pose the problem of whether γ=4 suffices. We establish a positive answer in the case where T has at most one node.
Salman Ghazal· AppliedMath· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
