@Book{616733836,
author="Nguyen, Ngoc Tuy",
title="Graph powers: hardness results, good characterizations and efficient algorithms",
year="2009",
abstract="Given a graph H = (V{\_}H,E{\_}H) and a positive integer k, the k-th power of H, written H^k, is the graph obtained from H by adding edges between any pair of vertices at distance at most k in H; formally, H^k = (V{\_}H, {\{}xy | 1 <= d{\_}H (x, y) <= k{\}}). A graph G is the k-th power of a graph H if G = H^k, and in this case, H is a k-th root of G. Our investigations deal with the computational complexity of recognizing k-th powers of general graphs as well as restricted graphs. This work provides new NP-completeness results, good characterizations and efficient algorithms for graph powers.",
note="vorgelegt von Ngoc Tuy Nguyen",
note="Rostock, Univ., Fak. f. Informatik u. Elektrotechnik, Diss., 2009",
url="http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2009-0206-0",
url="http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2009-0206-0&pdf",
url="http://nbn-resolving.de/urn:nbn:de:gbv:28-diss2009-0206-0",
url="http://rosdok.uni-rostock.de/metadata/rosdok_disshab_000000000350",
url="http://d-nb.info/100097877X/34",
language="English"
}