Graph powers
hardness results, good characterizations and efficient algorithms
Nguyen, Ngoc Tuy
1968-
aut
text
theses
Text
Hochschulschrift
gw
2009
monographic
XA-DE
2009
eng
text/html
application/pdf
pdf
Online-Ressource graph. Darst.
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.
vorgelegt von Ngoc Tuy Nguyen
Rostock, Univ., Fak. f. Informatik u. Elektrotechnik, Diss., 2009
510
31.12
http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2009-0206-0
http://rosdok.uni-rostock.de/resolve?urn=urn:nbn:de:gbv:28-diss2009-0206-0&pdf
http://nbn-resolving.de/urn:nbn:de:gbv:28-diss2009-0206-0
http://rosdok.uni-rostock.de/metadata/rosdok_disshab_000000000350
http://d-nb.info/100097877X/34
http://nbn-resolving.de/urn:nbn:de:gbv:28-diss2009-0206-0
Graph powers
2009
Druck-Ausgabe
(DE-627)612951650
Nguyen, Ngoc Tuy, 1968 -
urn:nbn:de:gbv:28-diss2009-0206-0
643190145
rakwb
DE-627
100119
616733836
20240710T223109.0
Converted from MARCXML to MODS version 3.8 using MARC21slim2MODS3-8_XSLT1-0.xsl
(Revision 1.174 20250328)
ger