Enumerate and Measure: Improving Parameter Budget Management
Identifieur interne : 001945 ( Istex/Curation ); précédent : 001944; suivant : 001946Enumerate and Measure: Improving Parameter Budget Management
Auteurs : Daniel Binkele-Raible [Allemagne] ; Henning Fernau [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.
Abstract
Abstract: Measure & Conquer (M&C) is the prominent technique for analyzing exact algorithms for computationally hard problems . It tries to balance worse and better situations within the algorithm analysis. Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to Vertex Cover, namely Connected Vertex Cover and Edge Dominating Set. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers and then producing solutions to the requested problem. Using M&C in this context will improve on the hitherto published running times, offering some unifying view. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.
Url:
DOI: 10.1007/978-3-642-17493-3_6
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001A62
Links to Exploration step
ISTEX:91DD40A8DDC779C446188605628AFD7C1FFDA200Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Enumerate and Measure: Improving Parameter Budget Management</title><author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name><affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: raible@informatik.uni-trier.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: fernau@informatik.uni-trier.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:91DD40A8DDC779C446188605628AFD7C1FFDA200</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-17493-3_6</idno><idno type="url">https://api.istex.fr/document/91DD40A8DDC779C446188605628AFD7C1FFDA200/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A62</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A62</idno><idno type="wicri:Area/Istex/Curation">001945</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Enumerate and Measure: Improving Parameter Budget Management</title><author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name><affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: raible@informatik.uni-trier.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Univ.Trier, 54286, Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: fernau@informatik.uni-trier.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2010</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">91DD40A8DDC779C446188605628AFD7C1FFDA200</idno><idno type="DOI">10.1007/978-3-642-17493-3_6</idno><idno type="ChapterID">6</idno><idno type="ChapterID">Chap6</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Measure & Conquer (M&C) is the prominent technique for analyzing exact algorithms for computationally hard problems . It tries to balance worse and better situations within the algorithm analysis. Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to Vertex Cover, namely Connected Vertex Cover and Edge Dominating Set. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers and then producing solutions to the requested problem. Using M&C in this context will improve on the hitherto published running times, offering some unifying view. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001945 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001945 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:91DD40A8DDC779C446188605628AFD7C1FFDA200
|texte= Enumerate and Measure: Improving Parameter Budget Management
}}
| This area was generated with Dilib version V0.6.31. |  |