mycoreobjectrosdok_disshab_0000000350rosdok_disshab_0000000350rosdokdisshabrosdok_derivate_00000041232023-08-08T10:01:25.202Z2010-01-15T12:56:31.697Zadministratorpublished1rosdok_derivate_0000004123truetruederivate_types:fulltextVolltextfulltextwf_edit_epub wf_register_epubstate:publishedstate:publishedveröffentlichtpublishedrosdok/id00000580616733836MODS updated during RosDok migration in June 2021DissertationHochschulschrift140242341Ngoc TuyNguyen1968-VerfasserInautGraph Powers: Hardness Results, Good Characterizations and Efficient AlgorithmsenProf. Dr.Van BangLeAkademischeR BetreuerIndgsProf. Dr.EgonWankeAkademischeR BetreuerIndgsProf. Dr.EkkehardKöhlerAkademischeR BetreuerIndgs10085032-7Universität RostockFakultät für Informatik und ElektrotechnikGrad-verleihende Institutiondgg10.18453/rosdok_id00000580http://purl.uni-rostock.de/rosdok/id00000580urn:nbn:de:gbv:28-diss2009-0206-0004 InformatikFakultät für Informatik und Elektrotechnikfrei zugänglich (Open Access)Lizenz Metadaten: CC0Nutzungsrechte erteiltalle Rechte vorbehaltenUniversität RostockRostock2009monographic20092009Universitätsbibliothek RostockRostock20102010Given 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.computational complexitygraph algorithmsgraph classesUniversitätsbibliothek Rostockhttp://purl.uni-rostock.de/rosdok/id00000580doctype:epubdoctype:epubDokumenttypDocument typedoctype:epub.dissertationdoctype:epub.dissertationDissertationdoctoral thesisdiniPublType:doctoralThesis diniPublType2022:PhDThesis XMetaDissPlusThesisLevel:thesis.doctoralinfo:eu-repo/semantics/doctoralThesisdocumentnatureOfContent:ppn_105825778natureOfContent:ppn_105825778HochschulschriftdiniPublType2022:DoctoralThesisdiniPublType2022:DoctoralThesisDissertation oder HabilitationDoctoral thesisDRIVERdiniPublType2022:PhDThesisdiniPublType2022:PhDThesisDissertationPhD thesisKDSF (Pu34)XMetaDissPlusThesisLevel:thesis.doctoralXMetaDissPlusThesisLevel:thesis.doctoralDoktorarbeitdoctoral thesisrfc5646:enrfc5646:enEnglischEnglishengengSDNB:004SDNB:004004 Informatik004 Data processing Computer sciencesinstitution:unirostockinstitution:unirostockUniversität RostockUniversity of RostockUniversität RostockUniversität RostockUni.Rostockhttp://d-nb.info/gnd/38329-6institution:unirostock.iefinstitution:unirostock.iefFakultät für Informatik und ElektrotechnikFaculty of Computer Science and Electrical EngineeringUniversität Rostock. Fakultät für Informatik und ElektrotechnikFakultät für Informatik<br />und ElektrotechnikUni.Rostock.Fakultaet.IEFhttp://d-nb.info/gnd/10085032-7accesscondition:openaccessaccesscondition:openaccessfrei zugänglich (Open Access)open accesshttp://purl.org/coar/access_right/c_abf2OAfreeinfo:eu-repo/semantics/openAccess[DE-28]Open Access$gControlled Vocabulary for Access Rights$uhttp://purl.org/coar/access_right/c_abf2licenseinfo:metadatalicenseinfo:metadataLizenzen für Metadatenlicenseinfo:metadata.cc0licenseinfo:metadata.cc0Lizenz Metadaten: CC0license metadata: CC0/creativecommons/p/zero/1.0/88x31.pnghttps://creativecommons.org/publicdomain/zero/1.0/licenseinfo:depositlicenseinfo:depositVeröffentlichungsgenehmigungpermission to storelicenseinfo:deposit.rightsgrantedlicenseinfo:deposit.rightsgrantedNutzungsrechte erteiltrights grantedlicenseinfo:worklicenseinfo:workWerkworklicenseinfo:work.rightsreservedlicenseinfo:work.rightsreservedalle Rechte vorbehaltenall rights reserved/creativecommons/r/reserved/0.9/88x31.png[DE-28]Urheberrechtsschutz 1.0$gRights Statements$uhttp://rightsstatements.org/vocab/InC/1.0/http://rightsstatements.org/vocab/InC/1.0/http://rightsstatements.org/vocab/InC/1.0/Graph Powers: Hardness Results, Good Characterizations and Efficient AlgorithmsGraph Powers: Hardness Results, Good Characterizations and Efficient Algorithmsgnd:140242341gnd:10085032-7gnd:140242341gnd:10085032-7rosdok_disshab_0000000350-d1411519e39gnd:140242341Ngoc Tuy NguyenNgoc Tuy Nguyenrosdok_disshab_0000000350-d1411519e60Prof. Dr. Van Bang LeProf. Dr. Van Bang Lerosdok_disshab_0000000350-d1411519e72Prof. Dr. Egon WankeProf. Dr. Egon Wankerosdok_disshab_0000000350-d1411519e84Prof. Dr. Ekkehard KöhlerProf. Dr. Ekkehard Köhlerrosdok_disshab_0000000350-d1411519e97gnd:10085032-7Universität Rostock Fakultät für Informatik und ElektrotechnikUniversität Rostock Fakultät für Informatik und ElektrotechnikNgoc Tuy NguyenProf. Dr. Van Bang LeProf. Dr. Egon WankeProf. Dr. Ekkehard KöhlerUniversität Rostock Fakultät für Informatik und ElektrotechnikNgoc Tuy NguyenProf. Dr. Van Bang LeProf. Dr. Egon WankeProf. Dr. Ekkehard KöhlerUniversität Rostock Fakultät für Informatik und ElektrotechnikNgoc Tuy NguyenRostockUniversität Rostockepub.dissertation10.18453/rosdok_id00000580http://purl.uni-rostock.de/rosdok/id00000580urn:nbn:de:gbv:28-diss2009-0206-0computational complexitygraph algorithmsgraph classesGiven 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.20092009epub.dissertation1 Dissertation_Nguyen_2009.pdf 896977 197d07c380d1f5b0b7d1b8bd4edc6da0 rosdok/id00000580616733836MODS updated during RosDok migration in June 2021DissertationHochschulschrift140242341Ngoc TuyNguyen1968-VerfasserInautGraph Powers: Hardness Results, Good Characterizations and Efficient AlgorithmsenProf. Dr.Van BangLeAkademischeR BetreuerIndgsProf. Dr.EgonWankeAkademischeR BetreuerIndgsProf. Dr.EkkehardKöhlerAkademischeR BetreuerIndgs10085032-7Universität RostockFakultät für Informatik und ElektrotechnikGrad-verleihende Institutiondgg10.18453/rosdok_id00000580http://purl.uni-rostock.de/rosdok/id00000580urn:nbn:de:gbv:28-diss2009-0206-0004 InformatikFakultät für Informatik und Elektrotechnikfrei zugänglich (Open Access)Lizenz Metadaten: CC0Nutzungsrechte erteiltalle Rechte vorbehaltenUniversität RostockRostock2009monographic20092009Universitätsbibliothek RostockRostock20102010Given 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.computational complexitygraph algorithmsgraph classesUniversitätsbibliothek Rostockhttp://purl.uni-rostock.de/rosdok/id00000580 2010-01-15T12:56:31.697Z 2023-08-08T10:01:25.202Z 2023-08-18T10:01:25.206Z {"identifier":"rosdok/id00000580","type":"local_id","additional":"","service":"MCRLocalID","created":"2018-06-30T12:41:52.351Z"} {"identifier":"http://purl.uni-rostock.de/rosdok/id00000580","type":"purl","additional":"","service":"RosDokPURL","created":"2018-06-30T12:41:52.472Z","registered":"2018-06-30T12:41:52.472Z"} {"identifier":"10.18453/rosdok_id00000580","type":"doi","additional":"","service":"RosDokDOI","created":"2018-06-30T12:41:53.740Z","registered":"2018-06-30T12:41:53.740Z"} {"identifier":"urn:nbn:de:gbv:28-diss2009-0206-0","type":"dnbUrn","additional":"","service":"RosDokURN","created":"2018-06-30T12:41:52.354Z","registered":"2010-01-21T03:29:43.213Z"} administratorfulltextfile/rosdok_disshab_0000000350/rosdok_derivate_0000004123/Dissertation_Nguyen_2009.pdfGraph Powers: Hardness Results, Good Characterizations and Efficient AlgorithmsGraph Powers: Hardness Results, Good Characterizations and Efficient Algorithmsgnd:140242341gnd:10085032-7gnd:140242341gnd:10085032-7rosdok_disshab_0000000350-d1411519e39gnd:140242341Ngoc Tuy NguyenNgoc Tuy Nguyenrosdok_disshab_0000000350-d1411519e60Prof. Dr. Van Bang LeProf. Dr. Van Bang Lerosdok_disshab_0000000350-d1411519e72Prof. Dr. Egon WankeProf. Dr. Egon Wankerosdok_disshab_0000000350-d1411519e84Prof. Dr. Ekkehard KöhlerProf. Dr. Ekkehard Köhlerrosdok_disshab_0000000350-d1411519e97gnd:10085032-7Universität Rostock Fakultät für Informatik und ElektrotechnikUniversität Rostock Fakultät für Informatik und ElektrotechnikNgoc Tuy NguyenProf. Dr. Van Bang LeProf. Dr. Egon WankeProf. Dr. Ekkehard KöhlerUniversität Rostock Fakultät für Informatik und ElektrotechnikNgoc Tuy NguyenProf. Dr. Van Bang LeProf. Dr. Egon WankeProf. Dr. Ekkehard KöhlerUniversität Rostock Fakultät für Informatik und ElektrotechnikNgoc Tuy NguyenRostockUniversität Rostockepub.dissertation10.18453/rosdok_id00000580http://purl.uni-rostock.de/rosdok/id00000580urn:nbn:de:gbv:28-diss2009-0206-0computational complexitygraph algorithmsgraph classesGiven 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.20092009[xslt]Saxonrosdok/id00000580https://purl.uni-rostock.de/rosdok/id0000058061673383610.18453/rosdok_id00000580urn:nbn:de:gbv:28-diss2009-0206-0Ngoc Tuy NguyenNguyen Ngoc TuyGraph Powers: Hardness Results, Good Characterizations and Efficient AlgorithmsDissertationdoctoral thesisUniversität Rostock, 2009Given 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…Ngoc Tuy NguyenGraph Powers: Hardness Results, Good Characterizations and Efficient AlgorithmsUniversitätsbibliothek Rostockhttp://purl.uni-rostock.de/rosdok/id00000580140242341Ngoc TuyNguyen1968-VerfasserInautProf. Dr.Van BangLeAkademischeR BetreuerIndgsProf. Dr.EgonWankeAkademischeR BetreuerIndgsProf. Dr.EkkehardKöhlerAkademischeR BetreuerIndgs10085032-7Universität RostockFakultät für Informatik und ElektrotechnikGrad-verleihende Institutiondgg[doi]10.18453/rosdok_id00000580[purl]http://purl.uni-rostock.de/rosdok/id00000580[urn]urn:nbn:de:gbv:28-diss2009-0206-0open_access20092009epoch:21th_centuryrfc5646:endoctype:epub.dissertationaccesscondition:openaccessSDNB:004institution:unirostock.iefstate:published