2026· International Symposium on Mathematical Foundations of Computer Science· pp. 73:1-73:16· 0 citations· 7 references
Computer Science
TL;DR
This work studies the unambiguous complexity of the Long Path problem on DAGs under parameterization and obtains an algorithm that achieves unambiguous and co-unambiguous O ( k log n ) space while running in time polynomial in both n and k.
This work restricts its attention to directed acyclic graphs (DAGs) and obtains a deterministic single-source reachability algorithm using $O(n \sqrt{n \log n})$ queries, based on a topological sort algorithm, and can also be adapted to compute single-source shortest paths in DAGs.
B. Bals, Matei Tinca, Yasamin Nazari· arXiv.org· 0 citations
It is proved that there exist DAGs for which any shortest-paths preserving integer reweighting requires weights of size $2^{\Omega(n)}$, even when the DAG has very simple structure.
Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges...
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.· 1 citation
It is shown that outer k-planar graphs have mim-width at most k+2, that graphs of cut-width at most k are outer 2k-planar, and that graphs of feedback edge set number at most k are outer 6k-planar, and that many graph parameters are incomparable with outer k-planarity, thereby clarifying its position within the graph p...
