@duerrschnabel

The approximation of maximum subgraph problems

, and . Automata, Languages and Programming, page 40--51. Berlin, Heidelberg, Springer Berlin Heidelberg, (1993)

Abstract

We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property $\pi$, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property $\pi$ on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.

Links and resources

BibTeX key:
10.1007/3-540-56939-1_60
search on:

Comments and Reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication