Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations

DOI10.1007/BF02241753zbMath0479.68040MaRDI QIDQ1162147

S. Singh

Publication date: 1982

Published in: Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Bibliographies for mathematics in general (00A15) Algorithms in computer science (68W99)

Related Items

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms, Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem, Complexity of discrete multicriteria problems, The asymptotic probabilistic behaviour of quadratic sum assignment problems, On the expected optimal value of random assignment problems: Experimental results and open questions, Some recent results in the analysis of greedy algorithms for assignment problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Matchings in random regular bipartite digraphs
• Hamiltonian circuits in random graphs
• A probabilistic minimum spanning tree algorithm
• On the expected behaviors of the Dijkstra's shortest path algorithm for complete graphs
• On Hamilton-cycles of random graphs
• On the Expected Value of a Random Assignment Problem
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Probabilistic Analysis of the Planar k-Median Problem
• Combinatorial Optimization: What is the State of the Art
• A probabilistic model for the analysis of the routing process for circuits
• On some adjunctions between the categories of adjunction-morphisms and monad-morphisms
• On colouring random graphs
• Maximum flow in probabilistic graphs-the discrete case
• Cliques in random graphs
• The Bottleneck Traveling Salesman Problem
• Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
• An Asymptotic, Probabilistic Analysis of a Routing Problem
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• A statistical approach to the tsp
• Randomly matchable graphs
• On the existence of a factor of degree one of a connected random graph
• Algorithm and Average-value Bounds for Assignment Problems
• Asymptotics and random matrices with row-sum and column sum-restrictions