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)
- 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
- In memoriam: Gerhard Woeginger (1964--2022)
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Concerning infeasibility of the wave functions of the universe
- Parallel family trees for transfer matrices in the Potts model
- Solving the job-shop scheduling problem optimally by dynamic programming
- An exact algorithm for the minimum dominating clique problem
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Width-parametrized SAT: time-space tradeoffs
- Parameterized algorithmics for linear arrangement problems
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Exact Algorithms for Edge Domination
- Strong partial clones and the time complexity of SAT problems
- Dynamic assignment of a multi-skilled workforce in job shops: an approximate dynamic programming approach
- Faster exact solutions for some NP-hard problems.
- A heuristic approach for the max-min diversity problem based on max-clique
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Branch and recharge: exact algorithms for generalized domination
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Fast algorithms for max independent set
- Solving connected dominating set faster than \(2^n\)
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- Recovery of signals from unordered partial frame coefficients
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
- Parameterized complexity and subexponential-time computability
- An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
- Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA
- Nondeterministic graph searching: from pathwidth to treewidth
- Restricted dynamic programming: a flexible framework for solving realistic VRPs
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Exact algorithms for edge domination
- An initial study of time complexity in infinite-domain constraint satisfaction
- Iterative compression and exact algorithms
- Fixed-parameter tractability and data reduction for multicut in trees
- 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
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)
