On the typical case complexity of graph optimization

DOI10.1016/j.dam.2005.05.007zbMath1091.68060OpenAlexW2133404696MaRDI QIDQ2581548

Andras Farago

Publication date: 10 January 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.007

zbMATH Keywords

Concentration of hardnessGraph optimizationNonuniform polynomial time algorithmTypical case complexity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Turing machines that take advice
• Random interval graphs
• The longest edge of the random minimal spanning tree
• The small-world phenomenon
• Average Case Complete Problems
• Random Plane Networks
• On Random Intersection Graphs: The Subgraph Problem
• The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1^d]
• A sharp concentration inequality with applications
• Random interval graphs
• On the connectivity of a random interval graph
• Node-and edge-deletion NP-complete problems
• Some remarks on the theory of graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item