Dynamic programming meets the principle of inclusion and exclusion
From MaRDI portal
Publication:1165163
DOI10.1016/0167-6377(82)90044-XzbMath0486.90083MaRDI QIDQ1165163
Publication date: 1982
Published in: Operations Research Letters (Search for Journal in Brave)
enumerationpackingsequencingassignmentcombination of dynamic programming and the principle of inclusion and exclusioncombinatorial existence problems
Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)
Related Items (37)
On Cutwidth Parameterized by Vertex Cover ⋮ Algorithms to count paths and cycles ⋮ Set multi-covering via inclusion-exclusion ⋮ Computing optimal Steiner trees in polynomial space ⋮ Parameterized complexity of superstring problems ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Finding and counting vertex-colored subtrees ⋮ A Hopf algebra for counting cycles ⋮ On partitioning a graph into two connected subgraphs ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ On cutwidth parameterized by vertex cover ⋮ Complexity of counting cycles using zeons ⋮ Collapsing Superstring Conjecture ⋮ A finite-difference sieve to count paths and cycles by length ⋮ A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ Open problems around exact algorithms ⋮ Solving the train marshalling problem by inclusion-exclusion ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ Inclusion/exclusion meets measure and conquer ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Enumerating simple paths from connected induced subgraphs ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Finding paths of length \(k\) in \(O^{*}(2^k)\) time ⋮ Exact algorithms for the Hamiltonian cycle problem in planar graphs ⋮ An exact algorithm for subgraph homeomorphism ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ A faster tree-decomposition based algorithm for counting linear extensions ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
This page was built for publication: Dynamic programming meets the principle of inclusion and exclusion
