×VerfasserIn
	140242341

Ngoc Tuy Nguyen

Graph Powers: Hardness Results, Good Characterizations and Efficient Algorithms

Universität Rostock, 2009

https://doi.org/10.18453/rosdok_id00000580

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.

doctoral thesis   free access