Loading…
A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler
In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location pr...
Saved in:
| Published in: | International journal of foundations of computer science 2017-12, Vol.28 (8), p.1021-1045 |
|---|---|
| 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-c314X-1a301d819fe3b1f505f16c374b573012e9928405d015756e4e206af6e3db951c3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c314X-1a301d819fe3b1f505f16c374b573012e9928405d015756e4e206af6e3db951c3 |
| container_end_page | 1045 |
| container_issue | 8 |
| container_start_page | 1021 |
| container_title | International journal of foundations of computer science |
| container_volume | 28 |
| creator | Trejo-Sánchez, Joel Antonio Fernández-Zepeda, José Alberto Ramírez-Pacheco, Julio César |
| description | In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length
O
(
log
n
)
bits. The execution time of this algorithm is
O
(
n
)
rounds or
O
(
n
2
)
time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring. |
| doi_str_mv | 10.1142/S012905411750037X |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2116146043</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2116146043</sourcerecordid><originalsourceid>FETCH-LOGICAL-c314X-1a301d819fe3b1f505f16c374b573012e9928405d015756e4e206af6e3db951c3</originalsourceid><addsrcrecordid>eNplkE9Lw0AQxRdRsNR-AG8LnqM7-y_NMRSthYpCLBQvYbPZbVfTpO4maP30JlS89DQw7_1meA-hayC3AJzeZQRoQgQHiAUhLF6foRHECYski9k5Gg1yNOiXaBKCKwgkkgkq5Ai9pTgzlY2yVhWucj-u3uC02jTetdsdto3HCj-pb7dTFabRi9Ifg8PV_XqmdNsFPPdqv8WrujQep_UBZ3pryq4y_gpdWFUFM_mbY7R6uH-dPUbL5_lili4jzYCvI1CMQDmFxBpWgBVEWJCaxbwQca9QkyR0yokoCYhYSMMNJVJZaVhZJAI0G6Ob4929bz47E9r8vel83b_MKYAELglnvQuOLu2bELyx-d73qfwhB5IPLeYnLfYMOTJfja_KoJ2pW2ed_kdPkV9p0nE_</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2116146043</pqid></control><display><type>article</type><title>A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler</title><source>TRIAL: World Scientific Journals</source><creator>Trejo-Sánchez, Joel Antonio ; Fernández-Zepeda, José Alberto ; Ramírez-Pacheco, Julio César</creator><creatorcontrib>Trejo-Sánchez, Joel Antonio ; Fernández-Zepeda, José Alberto ; Ramírez-Pacheco, Julio César</creatorcontrib><description>In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length
O
(
log
n
)
bits. The execution time of this algorithm is
O
(
n
)
rounds or
O
(
n
2
)
time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring.</description><identifier>ISSN: 0129-0541</identifier><identifier>EISSN: 1793-6373</identifier><identifier>DOI: 10.1142/S012905411750037X</identifier><language>eng</language><publisher>Singapore: World Scientific Publishing Company</publisher><subject>Algorithms</subject><ispartof>International journal of foundations of computer science, 2017-12, Vol.28 (8), p.1021-1045</ispartof><rights>2017, World Scientific Publishing Company</rights><rights>2017. World Scientific Publishing Company</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c314X-1a301d819fe3b1f505f16c374b573012e9928405d015756e4e206af6e3db951c3</citedby><cites>FETCH-LOGICAL-c314X-1a301d819fe3b1f505f16c374b573012e9928405d015756e4e206af6e3db951c3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.worldscientific.com/doi/reader/10.1142/S012905411750037X$$EPDF$$P50$$Gworldscientific$$H</linktopdf><link.rule.ids>314,780,784,3213,4872,27924,27925,55587</link.rule.ids></links><search><creatorcontrib>Trejo-Sánchez, Joel Antonio</creatorcontrib><creatorcontrib>Fernández-Zepeda, José Alberto</creatorcontrib><creatorcontrib>Ramírez-Pacheco, Julio César</creatorcontrib><title>A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler</title><title>International journal of foundations of computer science</title><description>In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length
O
(
log
n
)
bits. The execution time of this algorithm is
O
(
n
)
rounds or
O
(
n
2
)
time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring.</description><subject>Algorithms</subject><issn>0129-0541</issn><issn>1793-6373</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNplkE9Lw0AQxRdRsNR-AG8LnqM7-y_NMRSthYpCLBQvYbPZbVfTpO4maP30JlS89DQw7_1meA-hayC3AJzeZQRoQgQHiAUhLF6foRHECYski9k5Gg1yNOiXaBKCKwgkkgkq5Ai9pTgzlY2yVhWucj-u3uC02jTetdsdto3HCj-pb7dTFabRi9Ifg8PV_XqmdNsFPPdqv8WrujQep_UBZ3pryq4y_gpdWFUFM_mbY7R6uH-dPUbL5_lili4jzYCvI1CMQDmFxBpWgBVEWJCaxbwQca9QkyR0yokoCYhYSMMNJVJZaVhZJAI0G6Ob4929bz47E9r8vel83b_MKYAELglnvQuOLu2bELyx-d73qfwhB5IPLeYnLfYMOTJfja_KoJ2pW2ed_kdPkV9p0nE_</recordid><startdate>201712</startdate><enddate>201712</enddate><creator>Trejo-Sánchez, Joel Antonio</creator><creator>Fernández-Zepeda, José Alberto</creator><creator>Ramírez-Pacheco, Julio César</creator><general>World Scientific Publishing Company</general><general>World Scientific Publishing Co. Pte., Ltd</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>201712</creationdate><title>A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler</title><author>Trejo-Sánchez, Joel Antonio ; Fernández-Zepeda, José Alberto ; Ramírez-Pacheco, Julio César</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c314X-1a301d819fe3b1f505f16c374b573012e9928405d015756e4e206af6e3db951c3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Algorithms</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Trejo-Sánchez, Joel Antonio</creatorcontrib><creatorcontrib>Fernández-Zepeda, José Alberto</creatorcontrib><creatorcontrib>Ramírez-Pacheco, Julio César</creatorcontrib><collection>CrossRef</collection><jtitle>International journal of foundations of computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Trejo-Sánchez, Joel Antonio</au><au>Fernández-Zepeda, José Alberto</au><au>Ramírez-Pacheco, Julio César</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler</atitle><jtitle>International journal of foundations of computer science</jtitle><date>2017-12</date><risdate>2017</risdate><volume>28</volume><issue>8</issue><spage>1021</spage><epage>1045</epage><pages>1021-1045</pages><issn>0129-0541</issn><eissn>1793-6373</eissn><abstract>In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length
O
(
log
n
)
bits. The execution time of this algorithm is
O
(
n
)
rounds or
O
(
n
2
)
time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring.</abstract><cop>Singapore</cop><pub>World Scientific Publishing Company</pub><doi>10.1142/S012905411750037X</doi><tpages>25</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0129-0541 |
| ispartof | International journal of foundations of computer science, 2017-12, Vol.28 (8), p.1021-1045 |
| issn | 0129-0541 1793-6373 |
| language | eng |
| recordid | cdi_proquest_journals_2116146043 |
| source | TRIAL: World Scientific Journals |
| subjects | Algorithms |
| title | A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T22%3A26%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=A%20Self-Stabilizing%20Algorithm%20for%20a%20Maximal%202-Packing%20in%20a%20Cactus%20Graph%20Under%20Any%20Scheduler&rft.jtitle=International%20journal%20of%20foundations%20of%20computer%20science&rft.au=Trejo-S%C3%A1nchez,%20Joel%20Antonio&rft.date=2017-12&rft.volume=28&rft.issue=8&rft.spage=1021&rft.epage=1045&rft.pages=1021-1045&rft.issn=0129-0541&rft.eissn=1793-6373&rft_id=info:doi/10.1142/S012905411750037X&rft_dat=%3Cproquest_cross%3E2116146043%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c314X-1a301d819fe3b1f505f16c374b573012e9928405d015756e4e206af6e3db951c3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2116146043&rft_id=info:pmid/&rfr_iscdi=true |