# Certifying Algorithms for the Path Cover and Related Problems on Interval Graphs

Ontology type: schema:Chapter

### Chapter Info

DATE

2010

AUTHORS ABSTRACT

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves the answer has no compromised by a bug in the implementation. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to test whether a graph has a Hamiltonian cycle. A path cover of a graph is a family of vertex-disjoint paths that covers all vertices of the graph. The path cover problem is to find a path cover of a graph with minimum cardinality. The scattering number of a noncomplete connected graph G = (V,E) is defined by s(G) = max {ω(G − S) − |S|: S ⊆ V and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\omega(G-S)\geqslant 1\}$\end{document}, in which ω(G − S) denotes the number of components of the graph G − S. The scattering number problem is to determine the scattering number of a graph. A recognition problem of graphs is to decide whether a given input graph has a certain property. To the best of our knowledge, most published certifying algorithms are to solve the recognition problems for special classes of graphs. This paper presents O(n)-time certifying algorithms for the above three problems, including Hamiltonian cycle problem, path cover problem, and scattering number problem, on interval graphs given a set of n intervals with endpoints sorted. The certificates provided by our algorithms can be authenticated in O(n) time. More... »

PAGES

314-323

### Book

TITLE

Computational Science and Its Applications – ICCSA 2010

ISBN

978-3-642-12164-7
978-3-642-12165-4

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-12165-4_25

DOI

http://dx.doi.org/10.1007/978-3-642-12165-4_25

DIMENSIONS

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

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": "Department of Computer Science and Information Engineering, Chaoyang University of Technology, 413, Wufong, Taichung, Taiwan",
"id": "http://www.grid.ac/institutes/grid.411218.f",
"name": [
"Department of Computer Science and Information Engineering, Chaoyang University of Technology, 413, Wufong, Taichung, Taiwan"
],
"type": "Organization"
},
"familyName": "Hung",
"givenName": "Ruo-Wei",
"id": "sg:person.015643163537.30",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015643163537.30"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan"
],
"type": "Organization"
},
"familyName": "Chang",
"givenName": "Maw-Shang",
"id": "sg:person.013174232477.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
],
"type": "Person"
}
],
"datePublished": "2010",
"datePublishedReg": "2010-01-01",
"description": "A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves the answer has no compromised by a bug in the implementation. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to test whether a graph has a Hamiltonian cycle. A path cover of a graph is a family of vertex-disjoint paths that covers all vertices of the graph. The path cover problem is to find a path cover of a graph with minimum cardinality. The scattering number of a noncomplete connected graph G\u2009=\u2009(V,E) is defined by s(G)\u2009=\u2009 max {\u03c9(G\u2009\u2212\u2009S)\u2009\u2212\u2009|S|: S\u2009\u2286\u2009V and \\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}$\\omega(G-S)\\geqslant 1\\}$\\end{document}, in which \u03c9(G\u2009\u2212\u2009S) denotes the number of components of the graph G\u2009\u2212\u2009S. The scattering number problem is to determine the scattering number of a graph. A recognition problem of graphs is to decide whether a given input graph has a certain property. To the best of our knowledge, most published certifying algorithms are to solve the recognition problems for special classes of graphs. This paper presents O(n)-time certifying algorithms for the above three problems, including Hamiltonian cycle problem, path cover problem, and scattering number problem, on interval graphs given a set of n intervals with endpoints sorted. The certificates provided by our algorithms can be authenticated in O(n) time.",
"editor": [
{
"familyName": "Taniar",
"givenName": "David",
"type": "Person"
},
{
"familyName": "Gervasi",
"givenName": "Osvaldo",
"type": "Person"
},
{
"familyName": "Murgante",
"givenName": "Beniamino",
"type": "Person"
},
{
"familyName": "Pardede",
"givenName": "Eric",
"type": "Person"
},
{
"familyName": "Apduhan",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-12165-4_25",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-12164-7",
"978-3-642-12165-4"
],
"name": "Computational Science and Its Applications \u2013 ICCSA 2010",
"type": "Book"
},
"keywords": [
"recognition problem",
"Hamiltonian cycle problem",
"path cover problem",
"cover problem",
"interval graphs",
"cycle problem",
"noncomplete connected graph G",
"input graph",
"path cover",
"vertex-disjoint paths",
"algorithm",
"Hamiltonian cycle",
"graph",
"number problem",
"number of components",
"graph G",
"related problems",
"certificates",
"simple cycle",
"certain properties",
"special class",
"bugs",
"vertices",
"implementation",
"minimum cardinality",
"cardinality",
"set",
"path",
"number",
"knowledge",
"pieces",
"connected graph G",
"class",
"pieces of evidence",
"time",
"components",
"max",
"cycle",
"cover",
"properties",
"intervals",
"endpoints",
"family",
"evidence",
"problem",
"paper"
],
"name": "Certifying Algorithms for the Path Cover and Related Problems on Interval Graphs",
"pagination": "314-323",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1042380924"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-12165-4_25"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-12165-4_25",
"https://app.dimensions.ai/details/publication/pub.1042380924"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:57",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_35.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-12165-4_25"
}
]

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-642-12165-4_25'

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-642-12165-4_25'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-12165-4_25'

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-642-12165-4_25'

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

137 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves the answer has no compromised by a bug in the implementation. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to test whether a graph has a Hamiltonian cycle. A path cover of a graph is a family of vertex-disjoint paths that covers all vertices of the graph. The path cover problem is to find a path cover of a graph with minimum cardinality. The scattering number of a noncomplete connected graph G = (V,E) is defined by s(G) =  max {ω(G − S) − |S|: S ⊆ V and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\omega(G-S)\geqslant 1\}$\end{document}, in which ω(G − S) denotes the number of components of the graph G − S. The scattering number problem is to determine the scattering number of a graph. A recognition problem of graphs is to decide whether a given input graph has a certain property. To the best of our knowledge, most published certifying algorithms are to solve the recognition problems for special classes of graphs. This paper presents O(n)-time certifying algorithms for the above three problems, including Hamiltonian cycle problem, path cover problem, and scattering number problem, on interval graphs given a set of n intervals with endpoints sorted. The certificates provided by our algorithms can be authenticated in O(n) time.
7 schema:editor N1ae5c67d26414ecfae3c25b9a72b7e5b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5d18c669eb60477f92f0ab6ff037c7f4
12 schema:keywords Hamiltonian cycle
13 Hamiltonian cycle problem
14 algorithm
16 bugs
17 cardinality
18 certain properties
19 certificates
20 class
21 components
22 connected graph G
23 cover
24 cover problem
25 cycle
26 cycle problem
27 endpoints
28 evidence
29 family
30 graph
31 graph G
32 implementation
33 input graph
34 interval graphs
35 intervals
36 knowledge
37 max
38 minimum cardinality
39 noncomplete connected graph G
40 number
41 number of components
42 number problem
43 paper
44 path
45 path cover
46 path cover problem
47 pieces
48 pieces of evidence
49 problem
50 properties
51 recognition problem
52 related problems
53 set
54 simple cycle
55 special class
56 time
57 vertex-disjoint paths
58 vertices
59 schema:name Certifying Algorithms for the Path Cover and Related Problems on Interval Graphs
60 schema:pagination 314-323
62 Nef80f6f1dc024c08a4813273cf9f5bc4
63 schema:publisher Nc5725bd190e448d48dcc5fae5b5ffbb2
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042380924
65 https://doi.org/10.1007/978-3-642-12165-4_25
66 schema:sdDatePublished 2021-11-01T18:57
69 schema:url https://doi.org/10.1007/978-3-642-12165-4_25
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N19b201101032492e8b286356791f6e3c schema:familyName Gervasi
74 schema:givenName Osvaldo
75 rdf:type schema:Person
76 N1ae5c67d26414ecfae3c25b9a72b7e5b rdf:first N44c8898396784945843c3013a836cdb3
77 rdf:rest Na12e01281d904f06931e85a0673f2d01
78 N44c8898396784945843c3013a836cdb3 schema:familyName Taniar
79 schema:givenName David
80 rdf:type schema:Person
81 N5d18c669eb60477f92f0ab6ff037c7f4 schema:isbn 978-3-642-12164-7
82 978-3-642-12165-4
83 schema:name Computational Science and Its Applications – ICCSA 2010
84 rdf:type schema:Book
86 schema:value pub.1042380924
87 rdf:type schema:PropertyValue
88 N77eea0979e2a4fe9ad2f9186ac05123c schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
91 rdf:rest Nefbf2175e1b646768813fb4b9d22bdc8
92 N8a30c36523bd42898809ece7965b0707 rdf:first N99138486915f44e4aeb34d8ecf868ddc
93 rdf:rest Nd29a7c9e96a94fef8cfb3d3280be3966
94 N99138486915f44e4aeb34d8ecf868ddc schema:familyName Murgante
95 schema:givenName Beniamino
96 rdf:type schema:Person
97 Na12e01281d904f06931e85a0673f2d01 rdf:first N19b201101032492e8b286356791f6e3c
98 rdf:rest N8a30c36523bd42898809ece7965b0707
99 Nbfaf0d9166c04b50b1522ed69d73e508 schema:familyName Apduhan
101 rdf:type schema:Person
102 Nc007c4f9e3b546c8b00140981269ee12 schema:familyName Pardede
103 schema:givenName Eric
104 rdf:type schema:Person
105 Nc5725bd190e448d48dcc5fae5b5ffbb2 schema:name Springer Nature
106 rdf:type schema:Organisation
107 Nd29a7c9e96a94fef8cfb3d3280be3966 rdf:first Nc007c4f9e3b546c8b00140981269ee12
108 rdf:rest Nf14339e80d984f368691ee564c208dac
109 Nef80f6f1dc024c08a4813273cf9f5bc4 schema:name doi
110 schema:value 10.1007/978-3-642-12165-4_25
111 rdf:type schema:PropertyValue
112 Nefbf2175e1b646768813fb4b9d22bdc8 rdf:first sg:person.013174232477.45
113 rdf:rest rdf:nil
114 Nf14339e80d984f368691ee564c208dac rdf:first Nbfaf0d9166c04b50b1522ed69d73e508
115 rdf:rest rdf:nil
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
120 schema:name Computation Theory and Mathematics
121 rdf:type schema:DefinedTerm
122 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
123 schema:familyName Chang
124 schema:givenName Maw-Shang
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
126 rdf:type schema:Person
127 sg:person.015643163537.30 schema:affiliation grid-institutes:grid.411218.f
128 schema:familyName Hung
129 schema:givenName Ruo-Wei
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015643163537.30
131 rdf:type schema:Person
132 grid-institutes:grid.411218.f schema:alternateName Department of Computer Science and Information Engineering, Chaoyang University of Technology, 413, Wufong, Taichung, Taiwan
133 schema:name Department of Computer Science and Information Engineering, Chaoyang University of Technology, 413, Wufong, Taichung, Taiwan
134 rdf:type schema:Organization
135 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan
136 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan
137 rdf:type schema:Organization