Exact algorithms for NP-hard problems: A survey
From MaRDI portal
(Redirected from Exact algorithms for NP-hard problems: A survey)
Recommendations
- Exact exponential algorithms.
- An introduction to exponential time exact algorithms for solving NP-hard problems
- Faster exact solutions for some NP-hard problems. (Extended abstract)
- Faster exact solutions for some NP-hard problems.
- Exact Algorithms for Generalized Combinatorial Optimization Problems
Cited in
(only showing first 100 items - show all)- Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
- Parameterized algorithmics for linear arrangement problems
- Efficiency in exponential time for domination-type problems
- A heuristic approach for the max-min diversity problem based on max-clique
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- On two techniques of combining branching and treewidth
- Nondeterministic graph searching: from pathwidth to treewidth
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- A fixed-parameter tractability result for multicommodity demand flow in trees
- An \(O(n^{lg\,k}\cdot 2^{n/2})\) time and \(O(k\cdot 2^{n/k})\) space algorithm for certain NP-complete problems
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- Combining VNS with genetic algorithm to solve the one-to-one routing issue in road networks
- On comparing algorithms for the maximum clique problem
- Improving the Hopfield model performance when applied to the traveling salesman problem. A divide-and-conquer scheme
- Exact exponential algorithms for 3-machine flowshop scheduling problems
- Parameterized modal satisfiability
- Restricted dynamic programming: a flexible framework for solving realistic VRPs
- An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
- A note on the eternal dominating set problem
- Faster exact solutions for some NP-hard problems.
- Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA
- Exact algorithms for edge domination
- Exact algorithms for maximum independent set
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- Computing in combinatorial optimization
- Exact algorithms for counting 3-colorings of graphs
- In memoriam: Gerhard Woeginger (1964--2022)
- Moderate exponential-time algorithms for scheduling problems
- Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games
- Complexity and approximation results on the shared transportation problem
- Robust combinatorial optimization with locally budgeted uncertainty
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- Vertex coloring of a graph for memory constrained scenarios
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- Iterative compression and exact algorithms
- Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
- Faster exponential-time algorithms in graphs of bounded average degree
- A complexity and approximation framework for the maximization scaffolding problem
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Treewidth computation and extremal combinatorics
- Partition into triangles on bounded degree graphs
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Recovery of signals from unordered partial frame coefficients
- Minimizing the number of tardy jobs in two-machine settings with common due date
- Fast algorithms for max independent set
- Exact algorithms for problems related to the densest \(k\)-set problem
- An exact algorithm for the minimum dominating clique problem
- Open problems around exact algorithms
- A ``maximum node clustering problem
- Tree decomposition and discrete optimization problems: a survey
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- An improved exact algorithm for TSP in graphs of maximum degree 4
- Tight lower bounds for certain parameterized NP-hard problems
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Locally consistent constraint satisfaction problems
- A new algorithm for optimal 2-constraint satisfaction and its implications
- The traveling salesman problem with few inner points
- Efficient 3-SAT algorithms in the tile assembly model
- Improved worst-case complexity for the MIN 3-SET COVERING problem
- MP or not MP: that is the question
- Parameterized complexity and subexponential-time computability
- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
- Dual parameterization and parameterized approximability of subset graph problems
- Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
- Improving efficiency of 3-SAT-solving tile systems
- Partition into triangles on bounded degree graphs
- An introduction to exponential time exact algorithms for solving NP-hard problems
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Fixed-parameter tractability and data reduction for multicut in trees
- Parallel family trees for transfer matrices in the Potts model
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- Solving the job-shop scheduling problem optimally by dynamic programming
- Strong partial clones and the time complexity of SAT problems
- On the complexity of scaffolding problems: from cliques to sparse graphs
- An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
- Exact Algorithms for Edge Domination
- Exact Algorithms for Generalized Combinatorial Optimization Problems
- Deconstructing Intractability: A Case Study for Interval Constrained Coloring
- scientific article; zbMATH DE number 3915621 (Why is no real title available?)
- On an extension of the Sort \& Search method with application to scheduling theory
- Moderately exponential approximation for makespan minimization on related machines
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Exact algorithms for dominating set
- scientific article; zbMATH DE number 1206043 (Why is no real title available?)
- Covering moving points with anchored disks
- Bicolored independent sets and bicliques
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Faster exact solutions for some NP-hard problems. (Extended abstract)
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- On the \(k\)-rainbow domination in graphs with bounded tree-width
- The set cover conjecture and subgraph isomorphism with a tree pattern
- Merging nodes in search trees: an exact exponential algorithm for the single machine total tardiness scheduling problem
- Collective dynamics of phase-repulsive oscillators solves graph coloring problem
- On optimal approximability results for computing the strong metric dimension
- An initial study of time complexity in infinite-domain constraint satisfaction
- Faster Exact Bandwidth
- Comparing problem solving strategies for NP-hard optimization problems
- Solving NP-Complete Problems with Quantum Search
- Width-parametrized SAT: time-space tradeoffs
This page was built for publication: Exact algorithms for NP-hard problems: A survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4414647)
