ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > MARTIN WAHLÉN:
All reports by Author Martin Wahlén:

TR04-039 | 21st April 2004
Andrzej Lingas, Martin Wahlén

On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>



ISSN 1433-8092 | Imprint