Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics
Jialiang Li, Aneta Neumann, Frank Neumann +2
Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algor…
cs.DS2023
Limited Query Graph Connectivity Test
Mingyu Guo, Jialiang Li, Aneta Neumann +2
We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are…