Approximation algorithms for graph approximation problems

MaRDI QIDQ3115248zbMATH OpenFDO

Authors A. A. Navrotskaya, Victor Petrovich Il'ev, Svetlana Il'eva

Publication date 20 February 2012

zbMATH Keywords

approximation algorithmperformance guaranteegraph approximation problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for approximating graphs with bounded number of connected components
• Computational complexity of the problem of approximation by graphs with connected components of bounded size
• Computational complexity of the graph approximation problem
• Graph clustering with a constraint on cluster sizes
• Approximation algorithms for maximum dispersion

Cited in

(22)

• Better approximations of non-Hamiltonian graphs
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 5874803 (Why is no real title available?)
• Approximation algorithms for approximating graphs with bounded number of connected components
• Graph clustering with a constraint on cluster sizes
• Approximate algorithms for graph clustering problem
• On the polytope faces of the graph approximation problem
• Computational complexity of the problem of approximation by graphs with connected components of bounded size
• Approximate Mechanisms for the Graphical TSP and Other Graph-Traversal Problems
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• Approximation algorithms for requirement cut on graphs
• Exact and approximate algorithms for movement problems on (special classes of) graphs
• Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
• Approximation algorithms for graph augmentation
• Computational complexity of the graph approximation problem
• Parameterized Approximation Schemes Using Graph Widths
• On facet-inducing inequalities for combinatorial polytopes
• Approximation algorithms in graphs with known broadcast time of the base graph
• On a semi-supervised graph clustering problem
• Approximation algorithms for NP-complete problems on planar graphs
• Sublinear-time algorithms for approximating graph parameters

This page was built for publication: Approximation algorithms for graph approximation problems

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