scientific article; zbMATH DE number 1953201
From MaRDI portal
Publication:4414647
zbMATH Open1024.68529MaRDI QIDQ4414647FDOQ4414647
Authors: Gerhard J. Woeginger 
Publication date: 25 July 2003
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2570/25700185.htm
Title of this publication is not available (Why is that?)
Recommendations
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (only showing first 100 items - show all)
- An introduction to exponential time exact algorithms for solving NP-hard problems
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- Title not available (Why is that?)
- Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
- Finding a dominating set on bipartite graphs
- On exponential time lower bound of Knapsack under backtracking
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- A \(K\)-means supported reinforcement learning framework to multi-dimensional knapsack
- Tree decomposition and discrete optimization problems: a survey
- A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
- Comparing problem solving strategies for NP-hard optimization problems
- Locally consistent constraint satisfaction problems
- Multi-objective power distribution optimization using NSGA-II
- Strong triadic closure in cographs and graphs of low maximum degree
- Exact exponential algorithms for 3-machine flowshop scheduling problems
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Computational Short Cuts in Infinite Domain Constraint Satisfaction
- Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games
- On the complexity of scaffolding problems: from cliques to sparse graphs
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
- Robust combinatorial optimization with locally budgeted uncertainty
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- Vertex coloring of a graph for memory constrained scenarios
- On the shared transportation problem: computational hardness and exact approach
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- On the \(k\)-rainbow domination in graphs with bounded tree-width
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Faster exponential-time algorithms in graphs of bounded average degree
- A ``maximum node clustering problem
- Complexity and approximation results on the shared transportation problem
- Combining VNS with genetic algorithm to solve the one-to-one routing issue in road networks
- Partition into triangles on bounded degree graphs
- New Computational Paradigms
- A complexity and approximation framework for the maximization scaffolding problem
- An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
- On comparing algorithms for the maximum clique problem
- Merging nodes in search trees: an exact exponential algorithm for the single machine total tardiness scheduling problem
- Solving NP-Complete Problems with Quantum Search
- Title not available (Why is that?)
- Collective dynamics of phase-repulsive oscillators solves graph coloring problem
- When polynomial approximation meets exact computation
- Improved worst-case complexity for the MIN 3-SET COVERING problem
- 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
- Exact algorithms for counting 3-colorings of graphs
- A new taxonomy of global optimization algorithms
- The traveling salesman problem with few inner points
- Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion
- Computing in combinatorial optimization
- When polynomial approximation meets exact computation
- Parameterized modal satisfiability
- Improving efficiency of 3-SAT-solving tile systems
- Exact algorithms for maximum independent set
- Improving the Hopfield model performance when applied to the traveling salesman problem. A divide-and-conquer scheme
- Exact Algorithms for Generalized Combinatorial Optimization Problems
- Exact algorithms for problems related to the densest \(k\)-set problem
- Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
- Minimizing the number of tardy jobs in two-machine settings with common due date
- Moderate exponential-time algorithms for scheduling problems
- Moderately exponential approximation for makespan minimization on related machines
- On an extension of the Sort \& Search method with application to scheduling theory
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- An improved exact algorithm for TSP in graphs of maximum degree 4
- A note on the eternal dominating set problem
- Faster Exact Bandwidth
- Small spectral gap in the combinatorial Laplacian implies Hamiltonian
- Exact exponential algorithms.
- An improved exact algorithm for the domatic number problem
- Finding and enumerating Hamilton cycles in 4-regular graphs
- Exact algorithms for dominating set
- Partition into triangles on bounded degree graphs
- A note on exact algorithms for vertex ordering problems on graphs
- Cluster editing with locally bounded modifications
- Open problems around exact algorithms
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Tight lower bounds for certain parameterized NP-hard problems
- Covering moving points with anchored disks
- Exact algorithms for exact satisfiability and number of perfect matchings
- Complexity issues in color-preserving graph embeddings
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- On maximum independent sets in \(P_{5}\)-free graphs
- Reformulation of global constraints based on constraints checkers
- MP or not MP: that is the question
- Treewidth computation and extremal combinatorics
- Efficiency in exponential time for domination-type problems
- Dual parameterization and parameterized approximability of subset graph problems
- Optimal 2-constraint satisfaction via sum-product algorithms
- Title not available (Why is that?)
- On two techniques of combining branching and treewidth
- Bicolored independent sets and bicliques
- Sort and Search: exact algorithms for generalized domination
- Efficient 3-SAT algorithms in the tile assembly model
- Computing branchwidth via efficient triangulations and blocks
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- On optimal approximability results for computing the strong metric dimension
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- A hybrid exact algorithm for complete set partitioning
- Deconstructing Intractability: A Case Study for Interval Constrained Coloring
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4414647)
