10.18453/rosdok_id00000580 Nguyen, Ngoc Tuy Ngoc Tuy Nguyen http://d-nb.info/gnd/140242341 Universität Rostock 2009 004 Data processing Computer sciences 2009 en http://purl.uni-rostock.de/rosdok/id00000580 urn:nbn:de:gbv:28-diss2009-0206-0 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.