Hardness Results and Efficient Algorithms for Graph Powers

Nguyen Ngoc Tuy

Description

Hardness Results and Efficient Algorithms for Graph Powers Authors: Van Bang Le, Ngoc Tuy Nguyen University of Rostock, Germany Speaker: Ngoc Tuy Nguyen

• ngoc tuy


• efficient algorithms


• split graph


• graph powers


• van bang


• positive integer


• open problems

Sujets

• Split graph
• Natural number
• Open problem
• maths

Informations

• Publié par: pefav
• Nombre de lectures: 23
• Langue: English

Extrait

Hardness Results and Efficient Algorithms for Graph Powers Authors:Van Bang Le, NgocTuyNguyen University of Rostock, Germany Speaker:NgocTuyNguyen

ƒ ƒ ƒ ƒ Introduction Outline NP-completeness results for recognizing powers of graphs S Ef P fi L c I ie T nt G  a R l A go P ri H th a m n s d     f C or U  s B o E lv   i O n F g   S G Q R U AP A H R   E W  O IT F H  S  G T I R R O T N H  G ≥ LY 1   0 CHORDAL  Conclusion and open problems 2

ƒ Graph powers nIrtdocu k-thpower and k-throot of graph. •Let H = (V, E) be a graph. Let kbe a positive integer. The graph G= (V, E k )is thek-thpowerof H, and His called ak-throot of G, where E k = { xy| 1 ≤ d H (x,y) ≤ k}. The graph HSquare of H itno 3

ƒ Graph powers nIrtdocu k-thpower and k-throot of graph. •Let H = (V, E) be a graph. Let kbe a positive integer.The graph G= (V, E k )is thek-thpowerof H,and His called ak-throot of G, where E k = { xy| 1 ≤ d H (x,y) ≤ k}. The graph HSquare of HCube of H itno 4