Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > H-MATCHING:
Reports tagged with H-matching:
TR06-016 | 1st February 2006
Tomas Feder, Carlos Subi

Partition into $k$-vertex subgraphs of $k$-partite graphs

The $H$-matching problem asks to partition the vertices of an input graph $G$
into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$
isomorphic to $H$. The $H$-matching problem has been classified as polynomial
or NP-complete depending on whether $k\leq 2$ or not. We consider a variant
more >>>




ISSN 1433-8092 | Imprint