Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes

Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of supercomputing 2021-04, Vol.77 (4), p.4135-4150
Main Authors: Sundara Rajan, R., Kalinowski, Thomas, Klavžar, Sandi, Mokhtar, Hamid, Rajalaxmi, T. M.
Format: Article
Language:English
Subjects:
Algorithms
Cartesian coordinates
Compilers
Computer Science
Congestion
Dilation
Embedding
Fault tolerance
Graphs
Hypercubes
Interpreters
Lower bounds
Parallel processing
Processor Architectures
Programming Languages
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c319t-107514fcced1553313662843c43e5e7059fe3651e3d4d1380bc403c585dc93253
cites cdi_FETCH-LOGICAL-c319t-107514fcced1553313662843c43e5e7059fe3651e3d4d1380bc403c585dc93253
container_end_page 4150
container_issue 4
container_start_page 4135
container_title The Journal of supercomputing
container_volume 77
creator Sundara Rajan, R.
Kalinowski, Thomas
Klavžar, Sandi
Mokhtar, Hamid
Rajalaxmi, T. M.
description Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. Thus it becomes the first choice of topological structure of parallel processing and computing systems. In this paper, lower bounds for the dilation, wirelength, and edge congestion of an embedding of a graph into a hypercube are proved. Two of these bounds are expressed in terms of the bisection width. Applying these results, the dilation and wirelength of embedding of certain complete multipartite graphs, folded hypercubes, wheels, and specific Cartesian products are computed.
doi_str_mv 10.1007/s11227-020-03420-w
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2500468447</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2500468447</sourcerecordid><originalsourceid>FETCH-LOGICAL-c319t-107514fcced1553313662843c43e5e7059fe3651e3d4d1380bc403c585dc93253</originalsourceid><addsrcrecordid>eNp9kE1LxDAQhoMouK7-AU8Br1tNMkk_jrL4BQte9Gpok2m3y25Tk5bivzdrBW9eZmB43pl5X0KuObvljGV3gXMhsoQJljCQsU4nZMFVBgmTuTwlC1bEYa6kOCcXIewYYxIyWJCPjZvQ08qNnQ20dp7adl8OretWdGo97rFrhu2Klp2laBukxnUNhiNAXU3xUKG1bdfQxpf9NtC2GxzdfvXozVhhuCRndbkPePXbl-T98eFt_ZxsXp9e1vebxAAvhoSzTHFZG4OWKwXAIU1FLsFIQIUZU0WNkCqOYKXlkLPKSAZG5cqaAoSCJbmZ9_befY7xP71zo-_iSS1U9JrmUmaREjNlvAvBY6173x5K_6U508cc9Zyjjjnqnxz1FEUwi0KEo3f_t_of1TcRM3WT</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2500468447</pqid></control><display><type>article</type><title>Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes</title><source>Springer Nature</source><creator>Sundara Rajan, R. ; Kalinowski, Thomas ; Klavžar, Sandi ; Mokhtar, Hamid ; Rajalaxmi, T. M.</creator><creatorcontrib>Sundara Rajan, R. ; Kalinowski, Thomas ; Klavžar, Sandi ; Mokhtar, Hamid ; Rajalaxmi, T. M.</creatorcontrib><description>Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. Thus it becomes the first choice of topological structure of parallel processing and computing systems. In this paper, lower bounds for the dilation, wirelength, and edge congestion of an embedding of a graph into a hypercube are proved. Two of these bounds are expressed in terms of the bisection width. Applying these results, the dilation and wirelength of embedding of certain complete multipartite graphs, folded hypercubes, wheels, and specific Cartesian products are computed.</description><identifier>ISSN: 0920-8542</identifier><identifier>EISSN: 1573-0484</identifier><identifier>DOI: 10.1007/s11227-020-03420-w</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Algorithms ; Cartesian coordinates ; Compilers ; Computer Science ; Congestion ; Dilation ; Embedding ; Fault tolerance ; Graphs ; Hypercubes ; Interpreters ; Lower bounds ; Parallel processing ; Processor Architectures ; Programming Languages</subject><ispartof>The Journal of supercomputing, 2021-04, Vol.77 (4), p.4135-4150</ispartof><rights>Springer Science+Business Media, LLC, part of Springer Nature 2020</rights><rights>Springer Science+Business Media, LLC, part of Springer Nature 2020.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c319t-107514fcced1553313662843c43e5e7059fe3651e3d4d1380bc403c585dc93253</citedby><cites>FETCH-LOGICAL-c319t-107514fcced1553313662843c43e5e7059fe3651e3d4d1380bc403c585dc93253</cites><orcidid>0000-0002-1851-6334</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Sundara Rajan, R.</creatorcontrib><creatorcontrib>Kalinowski, Thomas</creatorcontrib><creatorcontrib>Klavžar, Sandi</creatorcontrib><creatorcontrib>Mokhtar, Hamid</creatorcontrib><creatorcontrib>Rajalaxmi, T. M.</creatorcontrib><title>Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes</title><title>The Journal of supercomputing</title><addtitle>J Supercomput</addtitle><description>Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. Thus it becomes the first choice of topological structure of parallel processing and computing systems. In this paper, lower bounds for the dilation, wirelength, and edge congestion of an embedding of a graph into a hypercube are proved. Two of these bounds are expressed in terms of the bisection width. Applying these results, the dilation and wirelength of embedding of certain complete multipartite graphs, folded hypercubes, wheels, and specific Cartesian products are computed.</description><subject>Algorithms</subject><subject>Cartesian coordinates</subject><subject>Compilers</subject><subject>Computer Science</subject><subject>Congestion</subject><subject>Dilation</subject><subject>Embedding</subject><subject>Fault tolerance</subject><subject>Graphs</subject><subject>Hypercubes</subject><subject>Interpreters</subject><subject>Lower bounds</subject><subject>Parallel processing</subject><subject>Processor Architectures</subject><subject>Programming Languages</subject><issn>0920-8542</issn><issn>1573-0484</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAQhoMouK7-AU8Br1tNMkk_jrL4BQte9Gpok2m3y25Tk5bivzdrBW9eZmB43pl5X0KuObvljGV3gXMhsoQJljCQsU4nZMFVBgmTuTwlC1bEYa6kOCcXIewYYxIyWJCPjZvQ08qNnQ20dp7adl8OretWdGo97rFrhu2Klp2laBukxnUNhiNAXU3xUKG1bdfQxpf9NtC2GxzdfvXozVhhuCRndbkPePXbl-T98eFt_ZxsXp9e1vebxAAvhoSzTHFZG4OWKwXAIU1FLsFIQIUZU0WNkCqOYKXlkLPKSAZG5cqaAoSCJbmZ9_befY7xP71zo-_iSS1U9JrmUmaREjNlvAvBY6173x5K_6U508cc9Zyjjjnqnxz1FEUwi0KEo3f_t_of1TcRM3WT</recordid><startdate>20210401</startdate><enddate>20210401</enddate><creator>Sundara Rajan, R.</creator><creator>Kalinowski, Thomas</creator><creator>Klavžar, Sandi</creator><creator>Mokhtar, Hamid</creator><creator>Rajalaxmi, T. M.</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0002-1851-6334</orcidid></search><sort><creationdate>20210401</creationdate><title>Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes</title><author>Sundara Rajan, R. ; Kalinowski, Thomas ; Klavžar, Sandi ; Mokhtar, Hamid ; Rajalaxmi, T. M.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c319t-107514fcced1553313662843c43e5e7059fe3651e3d4d1380bc403c585dc93253</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Algorithms</topic><topic>Cartesian coordinates</topic><topic>Compilers</topic><topic>Computer Science</topic><topic>Congestion</topic><topic>Dilation</topic><topic>Embedding</topic><topic>Fault tolerance</topic><topic>Graphs</topic><topic>Hypercubes</topic><topic>Interpreters</topic><topic>Lower bounds</topic><topic>Parallel processing</topic><topic>Processor Architectures</topic><topic>Programming Languages</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Sundara Rajan, R.</creatorcontrib><creatorcontrib>Kalinowski, Thomas</creatorcontrib><creatorcontrib>Klavžar, Sandi</creatorcontrib><creatorcontrib>Mokhtar, Hamid</creatorcontrib><creatorcontrib>Rajalaxmi, T. M.</creatorcontrib><collection>CrossRef</collection><jtitle>The Journal of supercomputing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Sundara Rajan, R.</au><au>Kalinowski, Thomas</au><au>Klavžar, Sandi</au><au>Mokhtar, Hamid</au><au>Rajalaxmi, T. M.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes</atitle><jtitle>The Journal of supercomputing</jtitle><stitle>J Supercomput</stitle><date>2021-04-01</date><risdate>2021</risdate><volume>77</volume><issue>4</issue><spage>4135</spage><epage>4150</epage><pages>4135-4150</pages><issn>0920-8542</issn><eissn>1573-0484</eissn><abstract>Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. One of the most efficient interconnection networks is the hypercube due to its structural regularity, potential for parallel computation of various algorithms, and the high degree of fault tolerance. Thus it becomes the first choice of topological structure of parallel processing and computing systems. In this paper, lower bounds for the dilation, wirelength, and edge congestion of an embedding of a graph into a hypercube are proved. Two of these bounds are expressed in terms of the bisection width. Applying these results, the dilation and wirelength of embedding of certain complete multipartite graphs, folded hypercubes, wheels, and specific Cartesian products are computed.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s11227-020-03420-w</doi><tpages>16</tpages><orcidid>https://orcid.org/0000-0002-1851-6334</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0920-8542
ispartof The Journal of supercomputing, 2021-04, Vol.77 (4), p.4135-4150
issn 0920-8542
1573-0484
language eng
recordid cdi_proquest_journals_2500468447
source Springer Nature
subjects Algorithms
Cartesian coordinates
Compilers
Computer Science
Congestion
Dilation
Embedding
Fault tolerance
Graphs
Hypercubes
Interpreters
Lower bounds
Parallel processing
Processor Architectures
Programming Languages
title Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T01%3A57%3A33IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Lower%20bounds%20for%20dilation,%20wirelength,%20and%20edge%20congestion%20of%20embedding%20graphs%20into%20hypercubes&rft.jtitle=The%20Journal%20of%20supercomputing&rft.au=Sundara%20Rajan,%20R.&rft.date=2021-04-01&rft.volume=77&rft.issue=4&rft.spage=4135&rft.epage=4150&rft.pages=4135-4150&rft.issn=0920-8542&rft.eissn=1573-0484&rft_id=info:doi/10.1007/s11227-020-03420-w&rft_dat=%3Cproquest_cross%3E2500468447%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c319t-107514fcced1553313662843c43e5e7059fe3651e3d4d1380bc403c585dc93253%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2500468447&rft_id=info:pmid/&rfr_iscdi=true