partition into isomorphic subgraphs

Article View: comp.theory

Article #2113

#2113

From: Unknown
Date: Wed, 28 Feb 1990 19:04

17 lines
1038 bytes

into Isomorphic Subgraphs." It states that given an instance (G,s)
where G and s are graphs, the decision problem as to whether or
not the graph G an be covered by one or more instances of graph s
(assuming no overlap) is NP-complete. The book goes on to state that
the decision problem is also NP-complete for an instance (G) where
s is a fixed graph of size >= 3.
From: sven@alv (Sven Dickinson)
Path: alv!sven

My question is: Is the later problem also NP-complete for G and s
planar?

please send responses to sven@alv.umd.edu

Thanks,

Sven

Technical Details

Message-ID: <4354@cvl.umd.edu>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!bloom-beacon!snorkelwacker!usc!brutus.cs.uiuc.edu!ux1.cso.uiuc.edu!tank!mimsy!cvl!Unknown

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!bloom-beacon!snorkelwacker!usc!brutus.cs.uiuc.edu!ux1.cso.uiuc.edu!tank!mimsy!cvl!Unknown
From: Unknown@cvl.umd.edu (Unknown)
Newsgroups: comp.theory
Subject: partition into isomorphic subgraphs
Message-ID: <4354@cvl.umd.edu>
Date: 28 Feb 90 19:04:47 GMT
Reply-To: sven@alv.UUCP (Sven Dickinson)
Organization: Center for Automation Research, Univ. of Md., College Park, MD 20742
Lines: 17