On the typical case complexity of graph optimization

DOI10.1016/J.DAM.2005.05.007MaRDI QIDQ2581548zbMATH OpenOpenAlexFDO

Authors 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) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 26845
• On the optimality of a simple strategy for searching graphs
• On the computational complexity of optimization convex covering problems of graphs
• scientific article; zbMATH DE number 219263
• On Graph Complexity
• Space complexity of optimization problems in planar graphs
• scientific article; zbMATH DE number 3876594
• Approximation algorithms for multi-parameter graph optimization problems

Cites work

• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1286037 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1340281 (Why is no real title available?)
• scientific article; zbMATH DE number 2050468 (Why is no real title available?)
• scientific article; zbMATH DE number 2080304 (Why is no real title available?)
• scientific article; zbMATH DE number 2084701 (Why is no real title available?)
• A sharp concentration inequality with applications
• Average Case Complete Problems
• Node-and edge-deletion NP-complete problems
• On Random Intersection Graphs: The Subgraph Problem
• On the connectivity of a random interval graph
• Random Plane Networks
• Random interval graphs
• Random interval graphs
• Some remarks on the theory of graphs
• The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]^d
• The longest edge of the random minimal spanning tree
• The small-world phenomenon: an algorithmic perspective
• Turing machines that take advice

Cited in

(3)

• Connections in Networks: Hardness of Feasibility Versus Optimality
• Worst case analysis of a greedy algorithm for graph thickness
• What makes an optimization problem hard?.

This page was built for publication: On the typical case complexity of graph optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581548)