1992 OntheApproximabilityoftheMaximu

• (Kann, 1992) ⇒ Viggo Kann. (1992). “On the Approximability of the Maximum Common Subgraph Problem.” In: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS 92). ISBN:978-3-540-46775-5 doi:10.1007/3-540-55210-3_198

Subject Headings: Maximum Common Subgraph Algorithm; Maximum Common Subgraph

Cited By

• http://scholar.google.com/scholar?q=%221992%22+On+the+Approximability+of+the+Maximum+Common+Subgraph+Problem
• http://dl.acm.org/citation.cfm?id=646508.694493&preflayout=flat#citedby

Quotes

Author Keywords

• Approximation; Graph Problems; Computational Complexity

Abstract

Some versions of the maximum common subgraph problem are studied and approximation algorithms are given. The maximum bounded common induced subgraph problem is shown to be Max SNP-hard and the maximum unbounded common induced subgraph problem is shown to be as hard to approximate as the maximum independent set problem. The maximum common induced connected subgraph problem is still harder to approximate and is shown to be NPO PB-complete, i.e. complete in the class of optimization problems with optimal value bounded by a polynomial.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1992 OntheApproximabilityoftheMaximu	Viggo Kann			On the Approximability of the Maximum Common Subgraph Problem				10.1007/3-540-55210-3_198		1992