Computational complexity of the graph approximation problem

DOI10.1134/S1990478907010012MaRDI QIDQ3115581zbMATH OpenFDO

Authors Alexander Ageev, Alexander Kononov, A. S. Televnin, Victor Petrovich Il'ev

Publication date 10 February 2012

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S1990478907010012

zbMATH Keywords

oriented graphnon-oriented graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Computational complexity of the problem of approximation by graphs with connected components of bounded size
• scientific article; zbMATH DE number 3999286
• On the complexity of approximating the independent set problem
• On the hardness of approximating minimization problems
• Approximation algorithms for graph approximation problems

Cited in

(23)

• Approximation algorithms for graph clustering problems with clusters of bounded size
• A computational complexity comparative study of graph tessellation problems
• On generic complexity of the graph clustering problem with bounded clusters
• 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
• Computational complexity of the problem of approximation by graphs with connected components of bounded size
• Method of conditional moments (MCM) for the chemical master equation
• Clustering complexity and an approximation algorithm for a version of the cluster editing problem
• The branch and cut method for the clique partitioning problem
• Approximation algorithms for graph approximation problems
• Estimation of discontinuous functions of two variables with unknown discontinuity lines (rectangular elements)
• 2-approximation algorithms for two graph clustering problems
• ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM
• Computing the differential of a graph: hardness, approximability and exact algorithms
• scientific article; zbMATH DE number 3876594 (Why is no real title available?)
• The generic complexity of the bounded problem of graphs clustering
• On facet-inducing inequalities for combinatorial polytopes
• On a semi-supervised graph clustering problem
• The complexity and approximability of minimum contamination problems
• One-sided weak dominance drawing
• On counting and approximation variants of the subgraph connecting problem
• Computational complexity of graphs

This page was built for publication: Computational complexity of the graph approximation problem

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