# A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion

Ontology type: schema:Chapter

### Chapter Info

DATE

2015-06-24

AUTHORS ABSTRACT

Measure & Conquer is an approach helpful for designing branching algorithms. A key point in the approach is how to design the measure. Given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} and an integer k, the Bounded Degree-one Deletion problem asks for if there exists a subset D of at most k vertices such that the degree of any vertex in G[V\D]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G[V\setminus D]$$\end{document} is upper bounded by one. Combining the parameter with a potential as the measure in Measure & Conquer, where the potential is a lower bound of the decrement of the parameter, we design a branching algorithm running in polynomial space and O(1.882k+|V||E|)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1.882^k+|V||E|)$$\end{document} time, which improves the current best parameterized complexity O∗(2k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(2^k)$$\end{document} of the problem. More... »

PAGES

469-480

### Book

TITLE

Computing and Combinatorics

ISBN

978-3-319-21397-2
978-3-319-21398-9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_37

DOI

http://dx.doi.org/10.1007/978-3-319-21398-9_37

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1024798906

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C"
],
"type": "Organization"
},
"familyName": "Wu",
"givenName": "Bang Ye",
"id": "sg:person.013045767237.23",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
],
"type": "Person"
}
],
"datePublished": "2015-06-24",
"datePublishedReg": "2015-06-24",
"description": "Measure & Conquer is an approach helpful for designing branching algorithms. A key point in the approach is how to design the measure. Given a graph G=(V,E)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G=(V,E)$$\\end{document} and an integer k, the Bounded Degree-one Deletion problem asks for if there exists a subset D of at most k vertices such that the degree of any vertex in G[V\\D]\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G[V\\setminus D]$$\\end{document} is upper bounded by one. Combining the parameter with a potential as the measure in Measure & Conquer, where the potential is a lower bound of the decrement of the parameter, we design a branching algorithm running in polynomial space and O(1.882k+|V||E|)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(1.882^k+|V||E|)$$\\end{document} time, which improves the current best parameterized complexity O\u2217(2k)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O^*(2^k)$$\\end{document} of the problem.",
"editor": [
{
"familyName": "Xu",
"givenName": "Dachuan",
"type": "Person"
},
{
"familyName": "Du",
"givenName": "Donglei",
"type": "Person"
},
{
"familyName": "Du",
"givenName": "Dingzhu",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-21398-9_37",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-319-21397-2",
"978-3-319-21398-9"
],
"name": "Computing and Combinatorics",
"type": "Book"
},
"keywords": [
"parameters",
"key points",
"algorithm",
"approach",
"degree",
"problem",
"potential",
"point",
"space",
"time",
"complexity",
"conquer approach",
"measures",
"conquer",
"Bounded Degree",
"Deletion problem",
"decrement",
"branching algorithm",
"polynomial space",
"Vertex Deletion",
"graph",
"vertices",
"integer k",
"deletion",
"subset D"
],
"name": "A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion",
"pagination": "469-480",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1024798906"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-21398-9_37"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-21398-9_37",
"https://app.dimensions.ai/details/publication/pub.1024798906"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-12-01T20:00",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_208.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-21398-9_37"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_37'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_37'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_37'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_37'

This table displays all metadata directly associated to this object as RDF triples.

95 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N0a5dba4688a546278be3ba9ebffb6f0b
4 schema:datePublished 2015-06-24
5 schema:datePublishedReg 2015-06-24
6 schema:description Measure & Conquer is an approach helpful for designing branching algorithms. A key point in the approach is how to design the measure. Given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} and an integer k, the Bounded Degree-one Deletion problem asks for if there exists a subset D of at most k vertices such that the degree of any vertex in G[V\D]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G[V\setminus D]$$\end{document} is upper bounded by one. Combining the parameter with a potential as the measure in Measure & Conquer, where the potential is a lower bound of the decrement of the parameter, we design a branching algorithm running in polynomial space and O(1.882k+|V||E|)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1.882^k+|V||E|)$$\end{document} time, which improves the current best parameterized complexity O∗(2k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(2^k)$$\end{document} of the problem.
7 schema:editor Nfa306814727248e5a9c98273779687f6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N1504fc11aa2e4db7974e493e3f03d53c
12 schema:keywords Bounded Degree
13 Deletion problem
14 Vertex Deletion
15 algorithm
16 approach
17 branching algorithm
18 complexity
19 conquer
20 conquer approach
21 decrement
22 degree
23 deletion
24 graph
25 integer k
26 key points
27 measures
28 parameters
29 point
30 polynomial space
31 potential
32 problem
33 space
34 subset D
35 time
36 vertices
37 schema:name A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
38 schema:pagination 469-480
39 schema:productId N09a3fb5afe4a42a29e7d42cc13eaab78
41 schema:publisher N1fa4c6243a4e4ca0b56021f061634419
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024798906
43 https://doi.org/10.1007/978-3-319-21398-9_37
44 schema:sdDatePublished 2021-12-01T20:00
46 schema:sdPublisher N46e0705791a646539d93080a2c584488
47 schema:url https://doi.org/10.1007/978-3-319-21398-9_37
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N09a3fb5afe4a42a29e7d42cc13eaab78 schema:name dimensions_id
52 schema:value pub.1024798906
53 rdf:type schema:PropertyValue
54 N0a5dba4688a546278be3ba9ebffb6f0b rdf:first sg:person.013045767237.23
55 rdf:rest rdf:nil
56 N1504fc11aa2e4db7974e493e3f03d53c schema:isbn 978-3-319-21397-2
57 978-3-319-21398-9
58 schema:name Computing and Combinatorics
59 rdf:type schema:Book
60 N1fa4c6243a4e4ca0b56021f061634419 schema:name Springer Nature
61 rdf:type schema:Organisation
62 N46e0705791a646539d93080a2c584488 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N6f5ff744f6af440090dd6913879926e1 schema:familyName Du
65 schema:givenName Donglei
66 rdf:type schema:Person
67 N7cfc87593e5848a49859cc2d3aced21e rdf:first N6f5ff744f6af440090dd6913879926e1
68 rdf:rest Nbca37d9459784f528024dceafe2f0037
69 N8003094e17a34275abdbd611b191e76b schema:familyName Du
70 schema:givenName Dingzhu
71 rdf:type schema:Person
72 Nbca37d9459784f528024dceafe2f0037 rdf:first N8003094e17a34275abdbd611b191e76b
73 rdf:rest rdf:nil
75 schema:value 10.1007/978-3-319-21398-9_37
76 rdf:type schema:PropertyValue
77 Ne073fc9b80f641bca472d21831a94206 schema:familyName Xu
78 schema:givenName Dachuan
79 rdf:type schema:Person
80 Nfa306814727248e5a9c98273779687f6 rdf:first Ne073fc9b80f641bca472d21831a94206
81 rdf:rest N7cfc87593e5848a49859cc2d3aced21e
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
86 schema:name Computation Theory and Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
89 schema:familyName Wu
90 schema:givenName Bang Ye
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
92 rdf:type schema:Person
93 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C
94 schema:name National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C
95 rdf:type schema:Organization