Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.
A Dynamic Programming Approach to Sequencing Problems
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 6roles
background 1polarities
background 1representative citing papers
MapReason-OSM supplies 6000 graph-verifiable instances across 12 mobility tasks on rendered OSM maps from 10 U.S. downtowns and shows that seven VLMs succeed at simple routing but perform near chance on cost-based facility placement and cross-zoom consistency.
Exhaustively parametrised feasibility-respecting quantum circuits can reach every feasible solution to problems like TSP with certainty using fixed parameters by leveraging group actions and generating sequences.
AtomTreeSearch embeds a neutral-atom quantum MWIS subroutine inside Monte Carlo Tree Search and matches or exceeds OR-Tools and simulated annealing on TSP instances up to 100 cities.
Improves exact algorithm for minimum edge deletion to connected cactus from O*(3^n) to O*(2^n), with O*(2^n n^{O(q)}) for q distinct nonnegative costs and O*(2^n (W+1)) pseudo-polynomial for integer costs summing to W.
Proves upper and lower bounds on the gap between minimum sum set cover cost and standard set cover size for hypergraphs and graphs, plus an FPT algorithm for bounded-rank hypergraphs parameterized by the sum cost.
citing papers explorer
-
Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.