Scheduling partially ordered jobs faster than \(2^n\)
From MaRDI portal
Publication:528859
DOI10.1007/s00453-012-9694-7zbMath1360.90124OpenAlexW2999396429MaRDI QIDQ528859
Jakub Onufry Wojtaszczyk, Michał Pilipczuk, Marcin Pilipczuk, Marek Cygan
Publication date: 17 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9694-7
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)
Related Items (5)
On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Unnamed Item ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Exact exponential algorithms for 3-machine flowshop scheduling problems
Cites Work
- Exact exponential algorithms.
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Exact and approximate bandwidth
- Capacitated domination faster than \(O(2^n)\)
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- Open problems around exact algorithms
- Exact Algorithm for the Maximum Induced Planar Subgraph Problem
- A measure & conquer approach for the analysis of exact algorithms
- Fourier meets M\"{o}bius: fast subset convolution
- Set Partitioning via Inclusion-Exclusion
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- Inclusion/Exclusion Meets Measure and Conquer
- An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
- Complexity of Scheduling under Precedence Constraints
- Parameterized and Exact Computation
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Bounds for Certain Multiprocessing Anomalies
- Optimal Sequencing of a Single Machine Subject to Precedence Constraints
- On the complexity of \(k\)-SAT
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Scheduling partially ordered jobs faster than \(2^n\)
