Loading…
Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpair...
Saved in:
Published in: | IEEE transactions on computers 2009-04, Vol.58 (4), p.528-540 |
---|---|
Main Authors: | , , |
Format: | Article |
Language: | English |
Subjects: | |
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-c311t-4f26baf3ac44ac5a70ba2b763f1a1098d21645102f03a362af7ffe7e97f31d233 |
---|---|
cites | cdi_FETCH-LOGICAL-c311t-4f26baf3ac44ac5a70ba2b763f1a1098d21645102f03a362af7ffe7e97f31d233 |
container_end_page | 540 |
container_issue | 4 |
container_start_page | 528 |
container_title | IEEE transactions on computers |
container_volume | 58 |
creator | Park, Jung-Heum Kim, Hee-Chul Lim, Hyeong-Seok |
description | A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpaired many-to-many disjoint path cover when each source can be joined to an arbitrary sink. In this paper, we discuss about paired and unpaired many-to-many disjoint path covers including their relationships, application to strong Hamiltonicity, and necessary conditions. And then, we give a construction scheme for paired many-to-many disjoint path covers in the graph H 0 oplus H 1 obtained from connecting two graphs H 0 and H 1 with |V(H 0 )| = |V(H 1 )| by |V(H 1 )| pairwise nonadjacent edges joining vertices in H 0 and vertices in H 1 , where H 0 = G 0 oplus G 1 and H 1 = G 2 oplus G 3 for some graphs G j . Using the construction, we show that every m-dimensional restricted HL-graph and recursive circulant G(2 m , 4) with f or less faulty elements have a paired k-DPC for any f and k ges 2 with f + 2k les m. |
doi_str_mv | 10.1109/TC.2008.160 |
format | article |
fullrecord | <record><control><sourceid>proquest_ieee_</sourceid><recordid>TN_cdi_ieee_primary_4620105</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>4620105</ieee_id><sourcerecordid>34443881</sourcerecordid><originalsourceid>FETCH-LOGICAL-c311t-4f26baf3ac44ac5a70ba2b763f1a1098d21645102f03a362af7ffe7e97f31d233</originalsourceid><addsrcrecordid>eNpd0L9LAzEYxvEgCtbq5OgSHFzk6psfl7sb5dqqULFDnUN6fUOvXC81SYX-96ZUHJze5cPLw5eQWwYjxqB6WtQjDlCOmIIzMmB5XmRVlatzMgBgZVYJCZfkKoQNACgO1YCM301_yKLLjpeO27BxbR_p3MQ1rd03-kDbnsY10rnHgH2D1Fk6NfsuHuikwy32MVyTC2u6gDe_d0g-p5NF_ZrNPl7e6udZ1gjGYiYtV0tjhWmkNE1uClgaviyUsMyk9eWKMyVzBtyCMEJxYwtrscCqsIKtuBBD8nD6u_Pua48h6m0bGuw606PbBy2klKIsWYL3_-DG7X2ftukyVylDwXlCjyfUeBeCR6t3vt0af9AM9DGnXtT6mFOnnEnfnXSLiH9SpooMcvEDA4FuYQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>856934722</pqid></control><display><type>article</type><title>Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements</title><source>IEEE Xplore (Online service)</source><creator>Park, Jung-Heum ; Kim, Hee-Chul ; Lim, Hyeong-Seok</creator><creatorcontrib>Park, Jung-Heum ; Kim, Hee-Chul ; Lim, Hyeong-Seok</creatorcontrib><description>A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpaired many-to-many disjoint path cover when each source can be joined to an arbitrary sink. In this paper, we discuss about paired and unpaired many-to-many disjoint path covers including their relationships, application to strong Hamiltonicity, and necessary conditions. And then, we give a construction scheme for paired many-to-many disjoint path covers in the graph H 0 oplus H 1 obtained from connecting two graphs H 0 and H 1 with |V(H 0 )| = |V(H 1 )| by |V(H 1 )| pairwise nonadjacent edges joining vertices in H 0 and vertices in H 1 , where H 0 = G 0 oplus G 1 and H 1 = G 2 oplus G 3 for some graphs G j . Using the construction, we show that every m-dimensional restricted HL-graph and recursive circulant G(2 m , 4) with f or less faulty elements have a paired k-DPC for any f and k ges 2 with f + 2k les m.</description><identifier>ISSN: 0018-9340</identifier><identifier>EISSN: 1557-9956</identifier><identifier>DOI: 10.1109/TC.2008.160</identifier><identifier>CODEN: ITCOB4</identifier><language>eng</language><publisher>New York: IEEE</publisher><subject>Bipartite graph ; Computer science ; Construction industry ; disjoint path covers ; Educational institutions ; Electronic mail ; fault Hamiltonicity ; Fault tolerance ; interconnection networks ; Joining processes ; Multiprocessor interconnection ; recursive circulants ; restricted HL-graphs ; strong Hamiltonicity</subject><ispartof>IEEE transactions on computers, 2009-04, Vol.58 (4), p.528-540</ispartof><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) 2009</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c311t-4f26baf3ac44ac5a70ba2b763f1a1098d21645102f03a362af7ffe7e97f31d233</citedby><cites>FETCH-LOGICAL-c311t-4f26baf3ac44ac5a70ba2b763f1a1098d21645102f03a362af7ffe7e97f31d233</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/4620105$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids></links><search><creatorcontrib>Park, Jung-Heum</creatorcontrib><creatorcontrib>Kim, Hee-Chul</creatorcontrib><creatorcontrib>Lim, Hyeong-Seok</creatorcontrib><title>Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements</title><title>IEEE transactions on computers</title><addtitle>TC</addtitle><description>A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpaired many-to-many disjoint path cover when each source can be joined to an arbitrary sink. In this paper, we discuss about paired and unpaired many-to-many disjoint path covers including their relationships, application to strong Hamiltonicity, and necessary conditions. And then, we give a construction scheme for paired many-to-many disjoint path covers in the graph H 0 oplus H 1 obtained from connecting two graphs H 0 and H 1 with |V(H 0 )| = |V(H 1 )| by |V(H 1 )| pairwise nonadjacent edges joining vertices in H 0 and vertices in H 1 , where H 0 = G 0 oplus G 1 and H 1 = G 2 oplus G 3 for some graphs G j . Using the construction, we show that every m-dimensional restricted HL-graph and recursive circulant G(2 m , 4) with f or less faulty elements have a paired k-DPC for any f and k ges 2 with f + 2k les m.</description><subject>Bipartite graph</subject><subject>Computer science</subject><subject>Construction industry</subject><subject>disjoint path covers</subject><subject>Educational institutions</subject><subject>Electronic mail</subject><subject>fault Hamiltonicity</subject><subject>Fault tolerance</subject><subject>interconnection networks</subject><subject>Joining processes</subject><subject>Multiprocessor interconnection</subject><subject>recursive circulants</subject><subject>restricted HL-graphs</subject><subject>strong Hamiltonicity</subject><issn>0018-9340</issn><issn>1557-9956</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2009</creationdate><recordtype>article</recordtype><recordid>eNpd0L9LAzEYxvEgCtbq5OgSHFzk6psfl7sb5dqqULFDnUN6fUOvXC81SYX-96ZUHJze5cPLw5eQWwYjxqB6WtQjDlCOmIIzMmB5XmRVlatzMgBgZVYJCZfkKoQNACgO1YCM301_yKLLjpeO27BxbR_p3MQ1rd03-kDbnsY10rnHgH2D1Fk6NfsuHuikwy32MVyTC2u6gDe_d0g-p5NF_ZrNPl7e6udZ1gjGYiYtV0tjhWmkNE1uClgaviyUsMyk9eWKMyVzBtyCMEJxYwtrscCqsIKtuBBD8nD6u_Pua48h6m0bGuw606PbBy2klKIsWYL3_-DG7X2ftukyVylDwXlCjyfUeBeCR6t3vt0af9AM9DGnXtT6mFOnnEnfnXSLiH9SpooMcvEDA4FuYQ</recordid><startdate>20090401</startdate><enddate>20090401</enddate><creator>Park, Jung-Heum</creator><creator>Kim, Hee-Chul</creator><creator>Lim, Hyeong-Seok</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>F28</scope><scope>FR3</scope></search><sort><creationdate>20090401</creationdate><title>Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements</title><author>Park, Jung-Heum ; Kim, Hee-Chul ; Lim, Hyeong-Seok</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c311t-4f26baf3ac44ac5a70ba2b763f1a1098d21645102f03a362af7ffe7e97f31d233</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Bipartite graph</topic><topic>Computer science</topic><topic>Construction industry</topic><topic>disjoint path covers</topic><topic>Educational institutions</topic><topic>Electronic mail</topic><topic>fault Hamiltonicity</topic><topic>Fault tolerance</topic><topic>interconnection networks</topic><topic>Joining processes</topic><topic>Multiprocessor interconnection</topic><topic>recursive circulants</topic><topic>restricted HL-graphs</topic><topic>strong Hamiltonicity</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Park, Jung-Heum</creatorcontrib><creatorcontrib>Kim, Hee-Chul</creatorcontrib><creatorcontrib>Lim, Hyeong-Seok</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998–Present</collection><collection>IEEE Electronic Library Online</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics & Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ANTE: Abstracts in New Technology & Engineering</collection><collection>Engineering Research Database</collection><jtitle>IEEE transactions on computers</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Park, Jung-Heum</au><au>Kim, Hee-Chul</au><au>Lim, Hyeong-Seok</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements</atitle><jtitle>IEEE transactions on computers</jtitle><stitle>TC</stitle><date>2009-04-01</date><risdate>2009</risdate><volume>58</volume><issue>4</issue><spage>528</spage><epage>540</epage><pages>528-540</pages><issn>0018-9340</issn><eissn>1557-9956</eissn><coden>ITCOB4</coden><abstract>A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpaired many-to-many disjoint path cover when each source can be joined to an arbitrary sink. In this paper, we discuss about paired and unpaired many-to-many disjoint path covers including their relationships, application to strong Hamiltonicity, and necessary conditions. And then, we give a construction scheme for paired many-to-many disjoint path covers in the graph H 0 oplus H 1 obtained from connecting two graphs H 0 and H 1 with |V(H 0 )| = |V(H 1 )| by |V(H 1 )| pairwise nonadjacent edges joining vertices in H 0 and vertices in H 1 , where H 0 = G 0 oplus G 1 and H 1 = G 2 oplus G 3 for some graphs G j . Using the construction, we show that every m-dimensional restricted HL-graph and recursive circulant G(2 m , 4) with f or less faulty elements have a paired k-DPC for any f and k ges 2 with f + 2k les m.</abstract><cop>New York</cop><pub>IEEE</pub><doi>10.1109/TC.2008.160</doi><tpages>13</tpages></addata></record> |
fulltext | fulltext |
identifier | ISSN: 0018-9340 |
ispartof | IEEE transactions on computers, 2009-04, Vol.58 (4), p.528-540 |
issn | 0018-9340 1557-9956 |
language | eng |
recordid | cdi_ieee_primary_4620105 |
source | IEEE Xplore (Online service) |
subjects | Bipartite graph Computer science Construction industry disjoint path covers Educational institutions Electronic mail fault Hamiltonicity Fault tolerance interconnection networks Joining processes Multiprocessor interconnection recursive circulants restricted HL-graphs strong Hamiltonicity |
title | Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements |
url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T14%3A49%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_ieee_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Many-to-Many%20Disjoint%20Path%20Covers%20in%20the%20Presence%20of%20Faulty%20Elements&rft.jtitle=IEEE%20transactions%20on%20computers&rft.au=Park,%20Jung-Heum&rft.date=2009-04-01&rft.volume=58&rft.issue=4&rft.spage=528&rft.epage=540&rft.pages=528-540&rft.issn=0018-9340&rft.eissn=1557-9956&rft.coden=ITCOB4&rft_id=info:doi/10.1109/TC.2008.160&rft_dat=%3Cproquest_ieee_%3E34443881%3C/proquest_ieee_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c311t-4f26baf3ac44ac5a70ba2b763f1a1098d21645102f03a362af7ffe7e97f31d233%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=856934722&rft_id=info:pmid/&rft_ieee_id=4620105&rfr_iscdi=true |