scientific article; zbMATH DE number 3936510

MaRDI QIDQ3707402zbMATH OpenFDO

Authors Richard Karp

Publication date 1984

zbMATH Keywords

analysis of algorithmsasymmetric versionEuclidean versionHamiltonian circuitsmatchingsmaximum cliquesminimum coloringsNP-hard combinatorial problemspartitioningrandom graphstraveling-salesman problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 3974320
• scientific article; zbMATH DE number 3932819
• scientific article; zbMATH DE number 3945879
• Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
• scientific article; zbMATH DE number 1246226

Cited in

(29)

• Probabilistic quality estimations for combinatorial optimization problems
• On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems
• A Probabilistic Analysis of Christofides’ Algorithm
• Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
• scientific article; zbMATH DE number 4205985 (Why is no real title available?)
• On some probability inequalities for some discrete optimization problems
• scientific article; zbMATH DE number 3932819 (Why is no real title available?)
• scientific article; zbMATH DE number 3939098 (Why is no real title available?)
• scientific article; zbMATH DE number 3945879 (Why is no real title available?)
• Probabilistic Algorithm for the Directed Traveling Salesman Problem
• scientific article; zbMATH DE number 3974291 (Why is no real title available?)
• scientific article; zbMATH DE number 3974320 (Why is no real title available?)
• scientific article; zbMATH DE number 168445 (Why is no real title available?)
• scientific article; zbMATH DE number 1961527 (Why is no real title available?)
• Probabilistic Combinatorial Optimization: Moments, Semidefinite Programming, and Asymptotic Bounds
• scientific article; zbMATH DE number 3997543 (Why is no real title available?)
• scientific article; zbMATH DE number 764392 (Why is no real title available?)
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• scientific article; zbMATH DE number 795219 (Why is no real title available?)
• scientific article; zbMATH DE number 1396596 (Why is no real title available?)
• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
• Towards a Systematic Evaluation of Generative Network Models
• On the external validity of average-case analyses of graph algorithms
• On the external validity of average-case analyses of graph algorithms
• A note on the complexity of a partition algorithm
• On the probabilistic behaviour of a heuristic algorithm for maximal Hamiltonian tours
• Solving chance-constrained combinatorial problems to optimality

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 Q3707402)