Loading…
A lower bound of the surviving rate of a planar graph with girth at least seven
Let G be a connected graph with n ≥2 vertices. Suppose that a fire breaks out at a vertex v of G . A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices...
Saved in:
| Published in: | Journal of combinatorial optimization 2014-05, Vol.27 (4), p.621-642 |
|---|---|
| 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-c288t-174412a7bd7901351b4c82785d19605b698baef2a5b07fc2e4683ba0467d77723 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c288t-174412a7bd7901351b4c82785d19605b698baef2a5b07fc2e4683ba0467d77723 |
| container_end_page | 642 |
| container_issue | 4 |
| container_start_page | 621 |
| container_title | Journal of combinatorial optimization |
| container_volume | 27 |
| creator | Wang, Weifan Finbow, Stephen Wang, Ping |
| description | Let
G
be a connected graph with
n
≥2 vertices. Suppose that a fire breaks out at a vertex
v
of
G
. A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn(
v
) denote the maximum number of vertices in
G
that the firefighter can save when a fire breaks out at vertex
v
. The surviving rate
ρ
(
G
) of
G
is defined to be ∑
v
∈
V
(
G
)
sn(
v
)/
n
2
, which is the average proportion of saved vertices.
In this paper, we show that if
G
is a planar graph with
n
≥2 vertices and having girth at least 7, then
. |
| doi_str_mv | 10.1007/s10878-012-9541-4 |
| format | article |
| fullrecord | <record><control><sourceid>crossref_sprin</sourceid><recordid>TN_cdi_crossref_primary_10_1007_s10878_012_9541_4</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_1007_s10878_012_9541_4</sourcerecordid><originalsourceid>FETCH-LOGICAL-c288t-174412a7bd7901351b4c82785d19605b698baef2a5b07fc2e4683ba0467d77723</originalsourceid><addsrcrecordid>eNp9kM1qwzAQhEVpoWnaB-hNL6B2V5Ys-RhC_yCQS3sWki07Dq5tJMehb1-Z9NzL7jDsLMNHyCPCEwKo54iglWaAnBVSIBNXZIVSZYxrnV8nnWnO8gLkLbmL8QgASYsV2W9oN5x9oG449RUdajodPI2nMLdz2zc02MkvrqVjZ3sbaBPseKDndjrQpg1p2ol23saJRj_7_p7c1LaL_uFvr8nX68vn9p3t9m8f282OlanQxFAJgdwqV6kCMJPoRKm50rLCIgfp8kI762tupQNVl9yLXGfOgshVpZTi2Zrg5W8ZhhiDr80Y2m8bfgyCWYiYCxGTiJiFiBEpwy-ZmG77xgdzHE6hTzX_Cf0CECRimg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>A lower bound of the surviving rate of a planar graph with girth at least seven</title><source>Springer Nature</source><creator>Wang, Weifan ; Finbow, Stephen ; Wang, Ping</creator><creatorcontrib>Wang, Weifan ; Finbow, Stephen ; Wang, Ping</creatorcontrib><description>Let
G
be a connected graph with
n
≥2 vertices. Suppose that a fire breaks out at a vertex
v
of
G
. A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn(
v
) denote the maximum number of vertices in
G
that the firefighter can save when a fire breaks out at vertex
v
. The surviving rate
ρ
(
G
) of
G
is defined to be ∑
v
∈
V
(
G
)
sn(
v
)/
n
2
, which is the average proportion of saved vertices.
In this paper, we show that if
G
is a planar graph with
n
≥2 vertices and having girth at least 7, then
.</description><identifier>ISSN: 1382-6905</identifier><identifier>EISSN: 1573-2886</identifier><identifier>DOI: 10.1007/s10878-012-9541-4</identifier><language>eng</language><publisher>Boston: Springer US</publisher><subject>Combinatorics ; Convex and Discrete Geometry ; Mathematical Modeling and Industrial Mathematics ; Mathematics ; Mathematics and Statistics ; Operations Research/Decision Theory ; Optimization ; Theory of Computation</subject><ispartof>Journal of combinatorial optimization, 2014-05, Vol.27 (4), p.621-642</ispartof><rights>Springer Science+Business Media, LLC 2012</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c288t-174412a7bd7901351b4c82785d19605b698baef2a5b07fc2e4683ba0467d77723</citedby><cites>FETCH-LOGICAL-c288t-174412a7bd7901351b4c82785d19605b698baef2a5b07fc2e4683ba0467d77723</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27903,27904</link.rule.ids></links><search><creatorcontrib>Wang, Weifan</creatorcontrib><creatorcontrib>Finbow, Stephen</creatorcontrib><creatorcontrib>Wang, Ping</creatorcontrib><title>A lower bound of the surviving rate of a planar graph with girth at least seven</title><title>Journal of combinatorial optimization</title><addtitle>J Comb Optim</addtitle><description>Let
G
be a connected graph with
n
≥2 vertices. Suppose that a fire breaks out at a vertex
v
of
G
. A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn(
v
) denote the maximum number of vertices in
G
that the firefighter can save when a fire breaks out at vertex
v
. The surviving rate
ρ
(
G
) of
G
is defined to be ∑
v
∈
V
(
G
)
sn(
v
)/
n
2
, which is the average proportion of saved vertices.
In this paper, we show that if
G
is a planar graph with
n
≥2 vertices and having girth at least 7, then
.</description><subject>Combinatorics</subject><subject>Convex and Discrete Geometry</subject><subject>Mathematical Modeling and Industrial Mathematics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Operations Research/Decision Theory</subject><subject>Optimization</subject><subject>Theory of Computation</subject><issn>1382-6905</issn><issn>1573-2886</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2014</creationdate><recordtype>article</recordtype><recordid>eNp9kM1qwzAQhEVpoWnaB-hNL6B2V5Ys-RhC_yCQS3sWki07Dq5tJMehb1-Z9NzL7jDsLMNHyCPCEwKo54iglWaAnBVSIBNXZIVSZYxrnV8nnWnO8gLkLbmL8QgASYsV2W9oN5x9oG449RUdajodPI2nMLdz2zc02MkvrqVjZ3sbaBPseKDndjrQpg1p2ol23saJRj_7_p7c1LaL_uFvr8nX68vn9p3t9m8f282OlanQxFAJgdwqV6kCMJPoRKm50rLCIgfp8kI762tupQNVl9yLXGfOgshVpZTi2Zrg5W8ZhhiDr80Y2m8bfgyCWYiYCxGTiJiFiBEpwy-ZmG77xgdzHE6hTzX_Cf0CECRimg</recordid><startdate>20140501</startdate><enddate>20140501</enddate><creator>Wang, Weifan</creator><creator>Finbow, Stephen</creator><creator>Wang, Ping</creator><general>Springer US</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20140501</creationdate><title>A lower bound of the surviving rate of a planar graph with girth at least seven</title><author>Wang, Weifan ; Finbow, Stephen ; Wang, Ping</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c288t-174412a7bd7901351b4c82785d19605b698baef2a5b07fc2e4683ba0467d77723</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2014</creationdate><topic>Combinatorics</topic><topic>Convex and Discrete Geometry</topic><topic>Mathematical Modeling and Industrial Mathematics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Operations Research/Decision Theory</topic><topic>Optimization</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Wang, Weifan</creatorcontrib><creatorcontrib>Finbow, Stephen</creatorcontrib><creatorcontrib>Wang, Ping</creatorcontrib><collection>CrossRef</collection><jtitle>Journal of combinatorial optimization</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Wang, Weifan</au><au>Finbow, Stephen</au><au>Wang, Ping</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A lower bound of the surviving rate of a planar graph with girth at least seven</atitle><jtitle>Journal of combinatorial optimization</jtitle><stitle>J Comb Optim</stitle><date>2014-05-01</date><risdate>2014</risdate><volume>27</volume><issue>4</issue><spage>621</spage><epage>642</epage><pages>621-642</pages><issn>1382-6905</issn><eissn>1573-2886</eissn><abstract>Let
G
be a connected graph with
n
≥2 vertices. Suppose that a fire breaks out at a vertex
v
of
G
. A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn(
v
) denote the maximum number of vertices in
G
that the firefighter can save when a fire breaks out at vertex
v
. The surviving rate
ρ
(
G
) of
G
is defined to be ∑
v
∈
V
(
G
)
sn(
v
)/
n
2
, which is the average proportion of saved vertices.
In this paper, we show that if
G
is a planar graph with
n
≥2 vertices and having girth at least 7, then
.</abstract><cop>Boston</cop><pub>Springer US</pub><doi>10.1007/s10878-012-9541-4</doi><tpages>22</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 1382-6905 |
| ispartof | Journal of combinatorial optimization, 2014-05, Vol.27 (4), p.621-642 |
| issn | 1382-6905 1573-2886 |
| language | eng |
| recordid | cdi_crossref_primary_10_1007_s10878_012_9541_4 |
| source | Springer Nature |
| subjects | Combinatorics Convex and Discrete Geometry Mathematical Modeling and Industrial Mathematics Mathematics Mathematics and Statistics Operations Research/Decision Theory Optimization Theory of Computation |
| title | A lower bound of the surviving rate of a planar graph with girth at least seven |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-25T18%3A28%3A39IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_sprin&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20lower%20bound%20of%20the%20surviving%20rate%20of%20a%20planar%20graph%20with%20girth%20at%20least%20seven&rft.jtitle=Journal%20of%20combinatorial%20optimization&rft.au=Wang,%20Weifan&rft.date=2014-05-01&rft.volume=27&rft.issue=4&rft.spage=621&rft.epage=642&rft.pages=621-642&rft.issn=1382-6905&rft.eissn=1573-2886&rft_id=info:doi/10.1007/s10878-012-9541-4&rft_dat=%3Ccrossref_sprin%3E10_1007_s10878_012_9541_4%3C/crossref_sprin%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c288t-174412a7bd7901351b4c82785d19605b698baef2a5b07fc2e4683ba0467d77723%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true |