On the typical case complexity of graph optimization

DOI10.1016/J.DAM.2005.05.007zbMATH Open1091.68060OpenAlexW2133404696MaRDI QIDQ2581548FDOQ2581548

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

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

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)

Cites Work

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

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)