Parameterized Complexity of the Firefighter Problem
Identifieur interne : 006357 ( Main/Curation ); précédent : 006356; suivant : 006358Parameterized Complexity of the Firefighter Problem
Auteurs : Cristina Bazgan [France] ; Morgan Chopin [France] ; Michael R. Fellows [Australie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
English descriptors
- KwdEn :
- Algorithm, Bipartite graphs, Busy gadget, Busy gadgets, Clique, Computable function, Cubic graphs, Discrete mathematics, Equivalent instance, Former problem, General graphs, Heidelberg, Input instance, Kernel, Maximum degree, Output instance, Parameter tractability, Parameterized, Parameterized complexity, Parameterized intractability, Parameterized problem, Parameterized problems, Planar graphs, Poly kernel, Polynomial kernel, Polynomial kernels, Polynomial time, Problem parameterized, Protection strategy, Reduction rule, Regular clique, Same number, Several cases, Subset, Time proof, Time step, Tractable, Valid strategy, Vertex, Vulnerable vertex.
- Teeft :
- Algorithm, Bipartite graphs, Busy gadget, Busy gadgets, Clique, Computable function, Cubic graphs, Discrete mathematics, Equivalent instance, Former problem, General graphs, Heidelberg, Input instance, Kernel, Maximum degree, Output instance, Parameter tractability, Parameterized, Parameterized complexity, Parameterized intractability, Parameterized problem, Parameterized problems, Planar graphs, Poly kernel, Polynomial kernel, Polynomial kernels, Polynomial time, Problem parameterized, Protection strategy, Reduction rule, Regular clique, Same number, Several cases, Subset, Time proof, Time step, Tractable, Valid strategy, Vertex, Vulnerable vertex.
Abstract
Abstract: In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that Saving k -Vertices and its dual Saving All But k -Vertices are both W[1]-hard for parameter k even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance, Saving k -Vertices is fixed-parameter tractable on planar graphs for parameter k. Moreover, we prove a lower bound to polynomial kernelization for Saving All But k -Vertices.
Url:
DOI: 10.1007/978-3-642-25591-5_66
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001518
- to stream Istex, to step Curation: Pour aller vers cette notice dans l'étape Curation :001518
- to stream Istex, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000776
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :006733
Links to Exploration step
ISTEX:70BD68B8E1DA56DBB7F6C3404A53D5FD25290EE3Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Parameterized Complexity of the Firefighter Problem</title>
<author><name sortKey="Bazgan, Cristina" sort="Bazgan, Cristina" uniqKey="Bazgan C" first="Cristina" last="Bazgan">Cristina Bazgan</name>
</author>
<author><name sortKey="Chopin, Morgan" sort="Chopin, Morgan" uniqKey="Chopin M" first="Morgan" last="Chopin">Morgan Chopin</name>
</author>
<author><name sortKey="Fellows, Michael R" sort="Fellows, Michael R" uniqKey="Fellows M" first="Michael R." last="Fellows">Michael R. Fellows</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:70BD68B8E1DA56DBB7F6C3404A53D5FD25290EE3</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-25591-5_66</idno>
<idno type="url">https://api.istex.fr/document/70BD68B8E1DA56DBB7F6C3404A53D5FD25290EE3/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001518</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001518</idno>
<idno type="wicri:Area/Istex/Curation">001518</idno>
<idno type="wicri:Area/Istex/Checkpoint">000776</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000776</idno>
<idno type="wicri:doubleKey">0302-9743:2011:Bazgan C:parameterized:complexity:of</idno>
<idno type="wicri:Area/Main/Merge">006733</idno>
<idno type="wicri:Area/Main/Curation">006357</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Parameterized Complexity of the Firefighter Problem</title>
<author><name sortKey="Bazgan, Cristina" sort="Bazgan, Cristina" uniqKey="Bazgan C" first="Cristina" last="Bazgan">Cristina Bazgan</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>LAMSADE, Université Paris-Dauphine</wicri:regionArea>
<wicri:noRegion>Université Paris-Dauphine</wicri:noRegion>
<wicri:noRegion>Université Paris-Dauphine</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>Institut Universitaire de France</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Chopin, Morgan" sort="Chopin, Morgan" uniqKey="Chopin M" first="Morgan" last="Chopin">Morgan Chopin</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>LAMSADE, Université Paris-Dauphine</wicri:regionArea>
<wicri:noRegion>Université Paris-Dauphine</wicri:noRegion>
<wicri:noRegion>Université Paris-Dauphine</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Fellows, Michael R" sort="Fellows, Michael R" uniqKey="Fellows M" first="Michael R." last="Fellows">Michael R. Fellows</name>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>Charles Darwin University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Australie</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2011</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Bipartite graphs</term>
<term>Busy gadget</term>
<term>Busy gadgets</term>
<term>Clique</term>
<term>Computable function</term>
<term>Cubic graphs</term>
<term>Discrete mathematics</term>
<term>Equivalent instance</term>
<term>Former problem</term>
<term>General graphs</term>
<term>Heidelberg</term>
<term>Input instance</term>
<term>Kernel</term>
<term>Maximum degree</term>
<term>Output instance</term>
<term>Parameter tractability</term>
<term>Parameterized</term>
<term>Parameterized complexity</term>
<term>Parameterized intractability</term>
<term>Parameterized problem</term>
<term>Parameterized problems</term>
<term>Planar graphs</term>
<term>Poly kernel</term>
<term>Polynomial kernel</term>
<term>Polynomial kernels</term>
<term>Polynomial time</term>
<term>Problem parameterized</term>
<term>Protection strategy</term>
<term>Reduction rule</term>
<term>Regular clique</term>
<term>Same number</term>
<term>Several cases</term>
<term>Subset</term>
<term>Time proof</term>
<term>Time step</term>
<term>Tractable</term>
<term>Valid strategy</term>
<term>Vertex</term>
<term>Vulnerable vertex</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Bipartite graphs</term>
<term>Busy gadget</term>
<term>Busy gadgets</term>
<term>Clique</term>
<term>Computable function</term>
<term>Cubic graphs</term>
<term>Discrete mathematics</term>
<term>Equivalent instance</term>
<term>Former problem</term>
<term>General graphs</term>
<term>Heidelberg</term>
<term>Input instance</term>
<term>Kernel</term>
<term>Maximum degree</term>
<term>Output instance</term>
<term>Parameter tractability</term>
<term>Parameterized</term>
<term>Parameterized complexity</term>
<term>Parameterized intractability</term>
<term>Parameterized problem</term>
<term>Parameterized problems</term>
<term>Planar graphs</term>
<term>Poly kernel</term>
<term>Polynomial kernel</term>
<term>Polynomial kernels</term>
<term>Polynomial time</term>
<term>Problem parameterized</term>
<term>Protection strategy</term>
<term>Reduction rule</term>
<term>Regular clique</term>
<term>Same number</term>
<term>Several cases</term>
<term>Subset</term>
<term>Time proof</term>
<term>Time step</term>
<term>Tractable</term>
<term>Valid strategy</term>
<term>Vertex</term>
<term>Vulnerable vertex</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that Saving k -Vertices and its dual Saving All But k -Vertices are both W[1]-hard for parameter k even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance, Saving k -Vertices is fixed-parameter tractable on planar graphs for parameter k. Moreover, we prove a lower bound to polynomial kernelization for Saving All But k -Vertices.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006357 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 006357 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Asie |area= AustralieFrV1 |flux= Main |étape= Curation |type= RBID |clé= ISTEX:70BD68B8E1DA56DBB7F6C3404A53D5FD25290EE3 |texte= Parameterized Complexity of the Firefighter Problem }}
This area was generated with Dilib version V0.6.33. |