Hardness Results and Efficient Algorithms for Graph Powers

pages

English

Documents

Écrit par
Nguyen Ngoc Tuy

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

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

Publié par

pefav

Langue

English

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 G≥LY1 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

Voir