Loading…
Minimum vertex cover in generalized random graphs with power law degree distribution
In this paper we study the approximability of the minimum vertex cover problem in power law graphs. In particular, we investigate the behavior of a standard 2-approximation algorithm together with a simple pre-processing step when the input is a random sample from a generalized random graph model wi...
Saved in:
| Published in: | Theoretical computer science 2016-09, Vol.647, p.101-111 |
|---|---|
| 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-c373t-e1564070e201279f76331d13119e68129b8efbdac893708c7ec5f03de47091e3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c373t-e1564070e201279f76331d13119e68129b8efbdac893708c7ec5f03de47091e3 |
| container_end_page | 111 |
| container_issue | |
| container_start_page | 101 |
| container_title | Theoretical computer science |
| container_volume | 647 |
| creator | Vignatti, André L. da Silva, Murilo V.G. |
| description | In this paper we study the approximability of the minimum vertex cover problem in power law graphs. In particular, we investigate the behavior of a standard 2-approximation algorithm together with a simple pre-processing step when the input is a random sample from a generalized random graph model with power law degree distribution. More precisely, if the probability of a vertex of degree i to be present in the graph is ci−β, where β>2 and c is a normalizing constant, the expected approximation ratio is 1+ζ(β)−1Liβ(e−ρ(β)), where ζ(β) is the Riemann Zeta function of β, Li(β) is the polylogarithmic special function of β and ρ(β)=Liβ−2(1e)ζ(β−1). |
| doi_str_mv | 10.1016/j.tcs.2016.08.002 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1835594877</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0304397516303899</els_id><sourcerecordid>1835594877</sourcerecordid><originalsourceid>FETCH-LOGICAL-c373t-e1564070e201279f76331d13119e68129b8efbdac893708c7ec5f03de47091e3</originalsourceid><addsrcrecordid>eNp9kDtPAzEQhC0EEiHwA-hc0txhn-_OtqhQxEsKoklvOfZe4uhe2L4E-PU4CjXb7BQzq50PoVtKckpofb_Lowl5kWRORE5IcYZmVHCZFYUsz9GMMFJmTPLqEl2FsCNpKl7P0Ord9a6bOrwHH-ELmyEJ7Hq8gR68bt0PWOx1b4cOb7wetwEfXNzicTgkX6sP2MLGA2DrQvRuPUU39NfootFtgJu_PUer56fV4jVbfry8LR6XmWGcxQxoVZeEE0hvF1w2vGaMWsoolVALWsi1gGZttRGScSIMB1M1hFkoOZEU2Bzdnc6OfvicIETVuWCgbXUPwxQUFayqZCk4T1Z6sho_hOChUaN3nfbfihJ1BKh2KgFUR4CKCJUApszDKQOpwt6BV8E46A1Y58FEZQf3T_oXqsR5IQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1835594877</pqid></control><display><type>article</type><title>Minimum vertex cover in generalized random graphs with power law degree distribution</title><source>ScienceDirect Journals</source><creator>Vignatti, André L. ; da Silva, Murilo V.G.</creator><creatorcontrib>Vignatti, André L. ; da Silva, Murilo V.G.</creatorcontrib><description>In this paper we study the approximability of the minimum vertex cover problem in power law graphs. In particular, we investigate the behavior of a standard 2-approximation algorithm together with a simple pre-processing step when the input is a random sample from a generalized random graph model with power law degree distribution. More precisely, if the probability of a vertex of degree i to be present in the graph is ci−β, where β>2 and c is a normalizing constant, the expected approximation ratio is 1+ζ(β)−1Liβ(e−ρ(β)), where ζ(β) is the Riemann Zeta function of β, Li(β) is the polylogarithmic special function of β and ρ(β)=Liβ−2(1e)ζ(β−1).</description><identifier>ISSN: 0304-3975</identifier><identifier>EISSN: 1879-2294</identifier><identifier>DOI: 10.1016/j.tcs.2016.08.002</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Approximation ; Approximation algorithms ; Britton random graph model ; Chung–Lu random graph model ; Computer simulation ; Constants ; Generalized random graph model ; Graphs ; Mathematical analysis ; Mathematical models ; Power law ; Power-law graphs ; Vertex cover problem</subject><ispartof>Theoretical computer science, 2016-09, Vol.647, p.101-111</ispartof><rights>2016 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c373t-e1564070e201279f76331d13119e68129b8efbdac893708c7ec5f03de47091e3</citedby><cites>FETCH-LOGICAL-c373t-e1564070e201279f76331d13119e68129b8efbdac893708c7ec5f03de47091e3</cites></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>Vignatti, André L.</creatorcontrib><creatorcontrib>da Silva, Murilo V.G.</creatorcontrib><title>Minimum vertex cover in generalized random graphs with power law degree distribution</title><title>Theoretical computer science</title><description>In this paper we study the approximability of the minimum vertex cover problem in power law graphs. In particular, we investigate the behavior of a standard 2-approximation algorithm together with a simple pre-processing step when the input is a random sample from a generalized random graph model with power law degree distribution. More precisely, if the probability of a vertex of degree i to be present in the graph is ci−β, where β>2 and c is a normalizing constant, the expected approximation ratio is 1+ζ(β)−1Liβ(e−ρ(β)), where ζ(β) is the Riemann Zeta function of β, Li(β) is the polylogarithmic special function of β and ρ(β)=Liβ−2(1e)ζ(β−1).</description><subject>Approximation</subject><subject>Approximation algorithms</subject><subject>Britton random graph model</subject><subject>Chung–Lu random graph model</subject><subject>Computer simulation</subject><subject>Constants</subject><subject>Generalized random graph model</subject><subject>Graphs</subject><subject>Mathematical analysis</subject><subject>Mathematical models</subject><subject>Power law</subject><subject>Power-law graphs</subject><subject>Vertex cover problem</subject><issn>0304-3975</issn><issn>1879-2294</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><recordid>eNp9kDtPAzEQhC0EEiHwA-hc0txhn-_OtqhQxEsKoklvOfZe4uhe2L4E-PU4CjXb7BQzq50PoVtKckpofb_Lowl5kWRORE5IcYZmVHCZFYUsz9GMMFJmTPLqEl2FsCNpKl7P0Ord9a6bOrwHH-ELmyEJ7Hq8gR68bt0PWOx1b4cOb7wetwEfXNzicTgkX6sP2MLGA2DrQvRuPUU39NfootFtgJu_PUer56fV4jVbfry8LR6XmWGcxQxoVZeEE0hvF1w2vGaMWsoolVALWsi1gGZttRGScSIMB1M1hFkoOZEU2Bzdnc6OfvicIETVuWCgbXUPwxQUFayqZCk4T1Z6sho_hOChUaN3nfbfihJ1BKh2KgFUR4CKCJUApszDKQOpwt6BV8E46A1Y58FEZQf3T_oXqsR5IQ</recordid><startdate>20160927</startdate><enddate>20160927</enddate><creator>Vignatti, André L.</creator><creator>da Silva, Murilo V.G.</creator><general>Elsevier B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20160927</creationdate><title>Minimum vertex cover in generalized random graphs with power law degree distribution</title><author>Vignatti, André L. ; da Silva, Murilo V.G.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c373t-e1564070e201279f76331d13119e68129b8efbdac893708c7ec5f03de47091e3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Approximation</topic><topic>Approximation algorithms</topic><topic>Britton random graph model</topic><topic>Chung–Lu random graph model</topic><topic>Computer simulation</topic><topic>Constants</topic><topic>Generalized random graph model</topic><topic>Graphs</topic><topic>Mathematical analysis</topic><topic>Mathematical models</topic><topic>Power law</topic><topic>Power-law graphs</topic><topic>Vertex cover problem</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Vignatti, André L.</creatorcontrib><creatorcontrib>da Silva, Murilo V.G.</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems 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><jtitle>Theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Vignatti, André L.</au><au>da Silva, Murilo V.G.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Minimum vertex cover in generalized random graphs with power law degree distribution</atitle><jtitle>Theoretical computer science</jtitle><date>2016-09-27</date><risdate>2016</risdate><volume>647</volume><spage>101</spage><epage>111</epage><pages>101-111</pages><issn>0304-3975</issn><eissn>1879-2294</eissn><abstract>In this paper we study the approximability of the minimum vertex cover problem in power law graphs. In particular, we investigate the behavior of a standard 2-approximation algorithm together with a simple pre-processing step when the input is a random sample from a generalized random graph model with power law degree distribution. More precisely, if the probability of a vertex of degree i to be present in the graph is ci−β, where β>2 and c is a normalizing constant, the expected approximation ratio is 1+ζ(β)−1Liβ(e−ρ(β)), where ζ(β) is the Riemann Zeta function of β, Li(β) is the polylogarithmic special function of β and ρ(β)=Liβ−2(1e)ζ(β−1).</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.tcs.2016.08.002</doi><tpages>11</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0304-3975 |
| ispartof | Theoretical computer science, 2016-09, Vol.647, p.101-111 |
| issn | 0304-3975 1879-2294 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_1835594877 |
| source | ScienceDirect Journals |
| subjects | Approximation Approximation algorithms Britton random graph model Chung–Lu random graph model Computer simulation Constants Generalized random graph model Graphs Mathematical analysis Mathematical models Power law Power-law graphs Vertex cover problem |
| title | Minimum vertex cover in generalized random graphs with power law degree distribution |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-02T10%3A59%3A53IST&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=Minimum%20vertex%20cover%20in%20generalized%20random%20graphs%20with%20power%20law%20degree%20distribution&rft.jtitle=Theoretical%20computer%20science&rft.au=Vignatti,%20Andr%C3%A9%20L.&rft.date=2016-09-27&rft.volume=647&rft.spage=101&rft.epage=111&rft.pages=101-111&rft.issn=0304-3975&rft.eissn=1879-2294&rft_id=info:doi/10.1016/j.tcs.2016.08.002&rft_dat=%3Cproquest_cross%3E1835594877%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c373t-e1564070e201279f76331d13119e68129b8efbdac893708c7ec5f03de47091e3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1835594877&rft_id=info:pmid/&rfr_iscdi=true |