zum Inhalt

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.

Dissertation   Freier Zugang    


OPACGVKDataCite Commons


alle Rechte vorbehalten

Das Werk darf ausschließlich nach den vom deutschen Urheberrechtsgesetz festgelegten Bedingungen genutzt werden.