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
-
MapReason-OSM: Can Vision-Language Models Make Graph-Verifiable Mobility Decisions from Street Maps ?
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.
-
Exhaustive and feasible parametrisation with applications to the travelling salesperson problem
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.
-
Quantum-enhanced Monte Carlo Tree Search framework for combinatorial optimization problems
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.
-
Exact Algorithms for Edge Deletion to Cactus Graphs and Weighted Variants
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.
-
Minimum Sum Set Cover: Structures and Algorithm
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.