Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

# Hardness Results and Efficient Algorithms for Graph Powers

De
41 pages
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

Voir plus Voir moins
##### maths

Vous aimerez aussi

Hardness Results and Efficient Algorithms for Graph PowersAuthors:Van Bang Le, NgocTuyNguyenUniversity of Rostock, GermanySpeaker:NgocTuyNguyen
IntroductionOutlineNP-completeness results for recognizing powers of graphsSEfPfiLcIieT ntG aRlAgoPriHthamnsd  fCorU sBoElv iOnFg  SGQRUAPAHR EW OITFH S GTIRROTNH GLY1 0CHORDAL Conclusion and open problems2
Graph powersnIrtdocuk-thpower and k-throot of graph.Let H = (V, E) be a graph. Let kbe a positive integer. The graph G= (V, Ek)is thek-thpowerof H, and His called ak-throot of G,where Ek= { xy| 1 dH(x,y)k}.The graph HSquare of Hitno3
Graph powersnIrtdocuk-thpower and k-throot of graph.Let H = (V, E) be a graph. Let kbe a positive integer.The graph G= (V, Ek)is thek-thpowerof H,and His called ak-throot of G,where Ek= { xy| 1 dH(x,y)k}.The graph HSquare of HCube of Hitno4