goto contents

Ngoc Tuy Nguyen

Graph Powers: Hardness Results, Good Characterizations and Efficient Algorithms

Universität Rostock, 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.

doctoral thesis   free access    


OPACGVKDataCite Commons


all rights reserved

This work may only be used under the terms of the German Copyright Law (Urheberrechtsgesetz).