The approximation of maximum subgraph problems
, and .
Automata, Languages and Programming, page 40--51. Berlin, Heidelberg, Springer Berlin Heidelberg, (1993)

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.
  • @duerrschnabel
  • @dblp
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).