Reducibility among combinatorial problems
From MaRDI portal
Publication:3565237
DOI10.1007/978-3-540-68279-0_8zbMATH Open1187.90014OpenAlexW1975442866MaRDI QIDQ3565237FDOQ3565237
Authors: Richard Karp 
Publication date: 3 June 2010
Published in: 50 Years of Integer Programming 1958-2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-68279-0_8
Recommendations
Combinatorial optimization (90C27) Collected or selected works; reprintings or translations of classics (01A75) History of operations research and mathematical programming (90-03)
Cited In (52)
- Finding Hamiltonian circuits in quasi-adjoint graphs
- Travelling salesman problem in tissue P systems with costs
- Notes on computational-to-statistical gaps: predictions using statistical physics
- Reductions among number theoretic problems
- Graph coloring approach with new upper bounds for the chromatic number: team building application
- Minimizing a sum of clipped convex functions
- Clustering in Hypergraphs to Minimize Average Edge Service Time
- Hitting subgraphs in \(P_4\)-tidy graphs
- Title not available (Why is that?)
- Continuous relaxations for the traveling salesman problem
- Combinatorics of reductions between equivalence relations
- A new formula for the decycling number of regular graphs
- Divide-and-price: a decomposition algorithm for solving large railway crew scheduling problems
- \textsc{max-cut} and containment relations in graphs
- Approximation algorithms for clustering with dynamic points
- Efficient Network Dismantling via Node Explosive Percolation*
- A lower bound for the breakpoint phylogeny problem
- Title not available (Why is that?)
- Forming \(k\) coalitions and facilitating relationships in social networks
- Control: a perspective
- Dynamic programming for the subset sum problem
- Finding a tree structure in a resolution proof is NP-complete
- On the integrality ratio of the subtour LP for Euclidean TSP
- Real-time solving of computationally hard problems using optimal algorithm portfolios
- Strategies for parallel unaware cleaners
- Integer programming models for the multidimensional assignment problem with star costs
- On the impact of running intersection inequalities for globally solving polynomial optimization problems
- Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem
- Complexity of Restricted Variants of Skolem and Related Problems
- On the optimal rank-1 approximation of matrices in the Chebyshev norm
- A wide-ranging computational comparison of high-performance graph colouring algorithms
- QUBO formulation for aircraft load optimization
- Balancing U-type assembly lines with human-robot collaboration
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- On the complexity of working set selection
- Finding the longest isometric cycle in a graph
- An attention model for the formation of collectives in real-world domains
- Rectangle packing with additional restrictions
- Policy analysis for administrative role-based access control
- Computing a feedback arc set using PageRank
- A faster cryptographer's Conspiracy Santa
- Approximate dynamic programming based on high dimensional model representation
- An ETH-Tight Exact Algorithm for Euclidean TSP
- A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
- Title not available (Why is that?)
- Pattern masking for dictionary matching: theory and practice
- Computational complexity of \(k\)-block conjugacy
- A dynamic programming algorithm for tree-like weighted set packing problem
- Title not available (Why is that?)
- Reducing hypergraph coloring to clique search
- Approximation algorithm for prize-collecting vertex cover with fairness constraints
- Incorporating a database of graphs into a proof assistant
This page was built for publication: Reducibility among combinatorial problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3565237)
