scientific article; zbMATH DE number 1953201

Publication date: 25 July 2003

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2570/25700185.htm

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (only showing first 100 items - show all)

Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games ⋮ MP or not MP: that is the question ⋮ Efficient 3-SAT algorithms in the tile assembly model ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Optimal 2-constraint satisfaction via sum-product algorithms ⋮ An improved exact algorithm for the domatic number problem ⋮ Complexity issues in color-preserving graph embeddings ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Reformulation of global constraints based on constraints checkers ⋮ Complexity and approximation results on the shared transportation problem ⋮ Improved worst-case complexity for the MIN 3-SET COVERING problem ⋮ Parallel family trees for transfer matrices in the Potts model ⋮ Combining VNS with genetic algorithm to solve the one-to-one routing issue in road networks ⋮ Solving the job-shop scheduling problem optimally by dynamic programming ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Treewidth computation and extremal combinatorics ⋮ Partition into triangles on bounded degree graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Robust combinatorial optimization with locally budgeted uncertainty ⋮ On comparing algorithms for the maximum clique problem ⋮ Recovery of signals from unordered partial frame coefficients ⋮ Minimizing the number of tardy jobs in two-machine settings with common due date ⋮ Why did the shape of your network change? (On detecting network anomalies via non-local curvatures) ⋮ Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA ⋮ On an extension of the Sort \& Search method with application to scheduling theory ⋮ Moderately exponential approximation for makespan minimization on related machines ⋮ Vertex coloring of a graph for memory constrained scenarios ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Exact algorithms for dominating set ⋮ A hybrid exact algorithm for complete set partitioning ⋮ Covering moving points with anchored disks ⋮ Fast algorithms for max independent set ⋮ Exact algorithms for edge domination ⋮ Improving the Hopfield model performance when applied to the traveling salesman problem. A divide-and-conquer scheme ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ Dual parameterization and parameterized approximability of subset graph problems ⋮ Bicolored independent sets and bicliques ⋮ Finding and enumerating Hamilton cycles in 4-regular graphs ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ Exact algorithms for problems related to the densest \(k\)-set problem ⋮ Small spectral gap in the combinatorial Laplacian implies Hamiltonian ⋮ An exact algorithm for the minimum dominating clique problem ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Exact exponential algorithms for 3-machine flowshop scheduling problems ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ On optimal approximability results for computing the strong metric dimension ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Open problems around exact algorithms ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ A ``maximum node clustering problem ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Finding a dominating set on bipartite graphs ⋮ Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming ⋮ Parameterized modal satisfiability ⋮ On exponential time lower bound of Knapsack under backtracking ⋮ Restricted dynamic programming: a flexible framework for solving realistic VRPs ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Exact algorithms for maximum independent set ⋮ On maximum independent sets in \(P_{5}\)-free graphs ⋮ Iterative compression and exact algorithms ⋮ Exact algorithms for the Hamiltonian cycle problem in planar graphs ⋮ Cluster editing with locally bounded modifications ⋮ Sort and Search: exact algorithms for generalized domination ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ An exact exponential branch-and-merge algorithm for the single machine total tardiness problem ⋮ Single-machine scheduling with release times, deadlines, setup times, and rejection ⋮ A note on the eternal dominating set problem ⋮ Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems ⋮ Improving Efficiency of 3-SAT-Solving Tile Systems ⋮ Parameterized algorithmics for linear arrangement problems ⋮ Efficiency in exponential time for domination-type problems ⋮ Partition into Triangles on Bounded Degree Graphs ⋮ A heuristic approach for the max-min diversity problem based on max-clique ⋮ Concerning infeasibility of the wave functions of the universe ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights ⋮ 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 ⋮ Computing in combinatorial optimization ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ A fixed-parameter tractability result for multicommodity demand flow in trees ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ In memoriam: Gerhard Woeginger (1964--2022) ⋮ Moderate exponential-time algorithms for scheduling 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 ⋮ Faster exponential-time algorithms in graphs of bounded average degree ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ A complexity and approximation framework for the maximization scaffolding problem ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

This page was built for publication: