{"id":{"repo_id":"unlv","oai_identifier":"oai:oasis.library.unlv.edu:rtds-1453"},"canonical_url":"https://search.dev.ndltd.org/etd/unlv/oai:oasis.library.unlv.edu:rtds-1453","repository":{"repo_id":"unlv","name":"University of Nevada - Las Vegas","base_url":"https://oasis.library.unlv.edu/do/oai/"},"display":{"title":"Fault-tolerance embedding of rings and arrays in star and pancake graphs","abstract":"The star and pancake graphs are useful interconnection networks for connecting processors in a parallel and distributed computing environment. The star network has been widely studied and is shown to possess attactive features like sublogarithmic diameter, node and edge symmetry and high resilience. The star/pancake interconnection graphs, {dollar}S\\sb{n}/P\\sb{n}{dollar} of dimension n have n! nodes connected by {dollar}{(n-1).n!\\over2}{dollar} edges. Due to their large number of nodes and interconnections, they are prone to failure of one or more nodes/edges; In this thesis, we present methods to embed Hamiltonian paths (H-path) and Hamiltonian cycles (H-cycle) in a star graph {dollar}S\\sb{n}{dollar} and pancake graph {dollar}P\\sb{n}{dollar} in a faulty environment. Such embeddings are important for solving computational problems, formulated for array and ring topologies, on star and pancake graphs. The models considered include single-processor failure, double-processor failure, and multiple-processor failures. All the models are applied to an H-cycle which is formed by visiting all the ({dollar}{n!\\over4!})\\ S\\sb4/P\\sb4{dollar}s in an {dollar}S\\sb{n}/P\\sb{n}{dollar} in a particular order. Each {dollar}S\\sb4/P\\sb4{dollar} has an entry node where the cycle/path enters that particular {dollar}S\\sb4/P\\sb4{dollar} and an exit node where the path leaves it. Distributed algorithms for embedding hamiltonian cycle in the presence of multiple faults, are also presented for both {dollar}S\\sb{n}{dollar} and {dollar}P\\sb{n}{dollar}.","abstract_html":"The star and pancake graphs are useful interconnection networks for connecting processors in a parallel and distributed computing environment. The star network has been widely studied and is shown to possess attactive features like sublogarithmic diameter, node and edge symmetry and high resilience. The star/pancake interconnection graphs, {dollar}S\\sb{n}/P\\sb{n}{dollar} of dimension n have n! nodes connected by {dollar}{(n-1).n!\\over2}{dollar} edges. Due to their large number of nodes and interconnections, they are prone to failure of one or more nodes/edges; In this thesis, we present methods to embed Hamiltonian paths (H-path) and Hamiltonian cycles (H-cycle) in a star graph {dollar}S\\sb{n}{dollar} and pancake graph {dollar}P\\sb{n}{dollar} in a faulty environment. Such embeddings are important for solving computational problems, formulated for array and ring topologies, on star and pancake graphs. The models considered include single-processor failure, double-processor failure, and multiple-processor failures. All the models are applied to an H-cycle which is formed by visiting all the ({dollar}{n!\\over4!})\\ S\\sb4/P\\sb4{dollar}s in an {dollar}S\\sb{n}/P\\sb{n}{dollar} in a particular order. Each {dollar}S\\sb4/P\\sb4{dollar} has an entry node where the cycle/path enters that particular {dollar}S\\sb4/P\\sb4{dollar} and an exit node where the path leaves it. Distributed algorithms for embedding hamiltonian cycle in the presence of multiple faults, are also presented for both {dollar}S\\sb{n}{dollar} and {dollar}P\\sb{n}{dollar}.","abstract_has_math":false,"creators":["Gajjala, Ramesh Reddy"],"institution":"University of Nevada, Las Vegas","degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Shahram Latifi"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1995,"date_issued":"1995-01-01T08:00:00Z","date_published":"1995-01-01T08:00:00Z","updated_at":"2026-07-24T05:24:31Z","subjects":[],"languages":["English"],"rights":["IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://oasis.library.unlv.edu/rtds/454"],"render_values":[{"text":"https://oasis.library.unlv.edu/rtds/454","href":"https://oasis.library.unlv.edu/rtds/454","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.25669/pgj1-yls7","outbound_label":"DOI","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shahram Latifi"]},{"key":"dc:creator","label":"Author","values":["Gajjala, Ramesh Reddy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:publisher","label":"Institution","values":["University of Nevada, Las Vegas"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["10.25669/pgj1-yls7","https://oasis.library.unlv.edu/rtds/454","https://oasis.library.unlv.edu/context/rtds/article/1453/viewcontent/uc.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The star and pancake graphs are useful interconnection networks for connecting processors in a parallel and distributed computing environment. The star network has been widely studied and is shown to possess attactive features like sublogarithmic diameter, node and edge symmetry and high resilience. The star/pancake interconnection graphs, {dollar}S\\sb{n}/P\\sb{n}{dollar} of dimension n have n! nodes connected by {dollar}{(n-1).n!\\over2}{dollar} edges. Due to their large number of nodes and interconnections, they are prone to failure of one or more nodes/edges; In this thesis, we present methods to embed Hamiltonian paths (H-path) and Hamiltonian cycles (H-cycle) in a star graph {dollar}S\\sb{n}{dollar} and pancake graph {dollar}P\\sb{n}{dollar} in a faulty environment. Such embeddings are important for solving computational problems, formulated for array and ring topologies, on star and pancake graphs. The models considered include single-processor failure, double-processor failure, and multiple-processor failures. All the models are applied to an H-cycle which is formed by visiting all the ({dollar}{n!\\over4!})\\ S\\sb4/P\\sb4{dollar}s in an {dollar}S\\sb{n}/P\\sb{n}{dollar} in a particular order. Each {dollar}S\\sb4/P\\sb4{dollar} has an entry node where the cycle/path enters that particular {dollar}S\\sb4/P\\sb4{dollar} and an exit node where the path leaves it. Distributed algorithms for embedding hamiltonian cycle in the presence of multiple faults, are also presented for both {dollar}S\\sb{n}{dollar} and {dollar}P\\sb{n}{dollar}."]},{"key":"dc:format","label":"Dc Format","values":["pdf"]},{"key":"dc:title","label":"Title","values":["Fault-tolerance embedding of rings and arrays in star and pancake graphs"]}]}],"canonical_facts":{"dc:contributor":["Shahram Latifi"],"dc:creator":["Gajjala, Ramesh Reddy"],"dc:description.abstract":["The star and pancake graphs are useful interconnection networks for connecting processors in a parallel and distributed computing environment. The star network has been widely studied and is shown to possess attactive features like sublogarithmic diameter, node and edge symmetry and high resilience. The star/pancake interconnection graphs, {dollar}S\\sb{n}/P\\sb{n}{dollar} of dimension n have n! nodes connected by {dollar}{(n-1).n!\\over2}{dollar} edges. Due to their large number of nodes and interconnections, they are prone to failure of one or more nodes/edges; In this thesis, we present methods to embed Hamiltonian paths (H-path) and Hamiltonian cycles (H-cycle) in a star graph {dollar}S\\sb{n}{dollar} and pancake graph {dollar}P\\sb{n}{dollar} in a faulty environment. Such embeddings are important for solving computational problems, formulated for array and ring topologies, on star and pancake graphs. The models considered include single-processor failure, double-processor failure, and multiple-processor failures. All the models are applied to an H-cycle which is formed by visiting all the ({dollar}{n!\\over4!})\\ S\\sb4/P\\sb4{dollar}s in an {dollar}S\\sb{n}/P\\sb{n}{dollar} in a particular order. Each {dollar}S\\sb4/P\\sb4{dollar} has an entry node where the cycle/path enters that particular {dollar}S\\sb4/P\\sb4{dollar} and an exit node where the path leaves it. Distributed algorithms for embedding hamiltonian cycle in the presence of multiple faults, are also presented for both {dollar}S\\sb{n}{dollar} and {dollar}P\\sb{n}{dollar}."],"dc:format":["pdf"],"dc:identifier":["10.25669/pgj1-yls7","https://oasis.library.unlv.edu/rtds/454","https://oasis.library.unlv.edu/context/rtds/article/1453/viewcontent/uc.pdf"],"dc:language":["English"],"dc:publisher":["University of Nevada, Las Vegas"],"dc:rights":["IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["Fault-tolerance embedding of rings and arrays in star and pancake graphs"],"dc:type":["Text"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-07-24T05:24:31Z"}