# On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs

Ontology type: schema:Chapter

### Chapter Info

DATE

2005

AUTHORS ABSTRACT

In this paper we consider the recognition of some probe graph classes. Given a class of graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{G}$ \end{document}, a graph G is a probe graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{G}$ \end{document} if its vertices can be partitioned into a set ℙ of probes and an independent set ℕ of nonprobes, such that G can be extended to a graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{G}$ \end{document} by adding edges between certain nonprobes. We show that there are polynomial-time recognition algorithms for probe cographs, probe P4-reducible graphs, probe P4-sparse graphs, and probe splitgraphs. More... »

PAGES

808-817

### Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-28061-3
978-3-540-31806-4

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11533719_82

DOI

http://dx.doi.org/10.1007/11533719_82

DIMENSIONS

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

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, National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C.",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C."
],
"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"
},
{
"affiliation": {
"alternateName": "Department of Mathematics and Computer Science, The university of Lethbridge, T1K 3M4, Alberta, Canada",
"id": "http://www.grid.ac/institutes/grid.47609.3c",
"name": [
"Department of Mathematics and Computer Science, The university of Lethbridge, T1K 3M4, Alberta, Canada"
],
"type": "Organization"
},
"familyName": "Kloks",
"givenName": "Ton",
"id": "sg:person.011052721431.97",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052721431.97"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "LITA, Universit\u00e9 de Metz, 57045, Metz Cedex 01, France",
"id": "http://www.grid.ac/institutes/grid.29172.3f",
"name": [
"LITA, Universit\u00e9 de Metz, 57045, Metz Cedex 01, France"
],
"type": "Organization"
},
"familyName": "Kratsch",
"givenName": "Dieter",
"id": "sg:person.07456026767.03",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07456026767.03"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics and Computer Science, The university of Lethbridge, T1K 3M4, Alberta, Canada",
"id": "http://www.grid.ac/institutes/grid.47609.3c",
"name": [
"Department of Mathematics and Computer Science, The university of Lethbridge, T1K 3M4, Alberta, Canada"
],
"type": "Organization"
},
"familyName": "Liu",
"givenName": "Jiping",
"id": "sg:person.012216324536.52",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012216324536.52"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, National Dong Hwa University, 974, Hualien, Taiwan, R.O.C.",
"id": "http://www.grid.ac/institutes/grid.260567.0",
"name": [
"Department of Computer Science and Information Engineering, National Dong Hwa University, 974, Hualien, Taiwan, R.O.C."
],
"type": "Organization"
},
"familyName": "Peng",
"givenName": "Sheng-Lung",
"id": "sg:person.013531324035.31",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31"
],
"type": "Person"
}
],
"datePublished": "2005",
"datePublishedReg": "2005-01-01",
"description": "In this paper we consider the recognition of some probe graph classes. Given a class of graphs \\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}\n$\\mathcal{G}$\n\\end{document}, a graph G is a probe graph of \\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}\n$\\mathcal{G}$\n\\end{document} if its vertices can be partitioned into a set \u2119 of probes and an independent set \u2115 of nonprobes, such that G can be extended to a graph of \\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}\n$\\mathcal{G}$\n\\end{document} by adding edges between certain nonprobes. We show that there are polynomial-time recognition algorithms for probe cographs, probe P4-reducible graphs, probe P4-sparse graphs, and probe splitgraphs.",
"editor": [
{
"familyName": "Wang",
"givenName": "Lusheng",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11533719_82",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-28061-3",
"978-3-540-31806-4"
],
"name": "Computing and Combinatorics",
"type": "Book"
},
"keywords": [
"probe graphs",
"certain nonprobes",
"recognition algorithm",
"polynomial-time recognition algorithm",
"probe cographs",
"P4-sparse graphs",
"graph classes",
"graph",
"P4-reducible graphs",
"class of graphs",
"nonprobes",
"perfect graphs",
"recognition",
"algorithm",
"splitgraphs",
"graph G",
"cographs",
"class",
"vertices",
"edge",
"probe",
"paper",
"probe graph classes",
"probe splitgraphs",
"Self-Complementary Classes"
],
"name": "On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs",
"pagination": "808-817",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1009768313"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11533719_82"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11533719_82",
"https://app.dimensions.ai/details/publication/pub.1009768313"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:52",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_233.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11533719_82"
}
]

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/11533719_82'

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/11533719_82'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11533719_82'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11533719_82'

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

122 TRIPLES      23 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N74dc3544419741849b7936a64e27735d
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description In this paper we consider the recognition of some probe graph classes. Given a class of graphs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{G}$ \end{document}, a graph G is a probe graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{G}$ \end{document} if its vertices can be partitioned into a set ℙ of probes and an independent set ℕ of nonprobes, such that G can be extended to a graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{G}$ \end{document} by adding edges between certain nonprobes. We show that there are polynomial-time recognition algorithms for probe cographs, probe P4-reducible graphs, probe P4-sparse graphs, and probe splitgraphs.
7 schema:editor Nc89f03ddf66c4a37b7be21052f5af166
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nba99847c7d5b49dc84ff3eabcf9fcf17
12 schema:keywords P4-reducible graphs
13 P4-sparse graphs
14 Self-Complementary Classes
15 algorithm
16 certain nonprobes
17 class
18 class of graphs
19 cographs
20 edge
21 graph
22 graph G
23 graph classes
24 nonprobes
25 paper
26 perfect graphs
27 polynomial-time recognition algorithm
28 probe
29 probe cographs
30 probe graph classes
31 probe graphs
32 probe splitgraphs
33 recognition
34 recognition algorithm
35 splitgraphs
36 vertices
37 schema:name On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs
38 schema:pagination 808-817
39 schema:productId N9bba94a88aa0413d9c71b22d049676d3
40 Naf05f30f6f6f4e7fbf6c3c48e7f34e38
41 schema:publisher N348cd2619326474bbfcf386df4d9032b
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009768313
43 https://doi.org/10.1007/11533719_82
44 schema:sdDatePublished 2021-11-01T18:52
46 schema:sdPublisher N711e97a6357543aea59e6b7df71e0cb6
47 schema:url https://doi.org/10.1007/11533719_82
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N348cd2619326474bbfcf386df4d9032b schema:name Springer Nature
52 rdf:type schema:Organisation
54 schema:givenName Lusheng
55 rdf:type schema:Person
56 N5938d3ef8788456f9b936cf9aa00813d rdf:first sg:person.012216324536.52
57 rdf:rest N5e945be52d814512a78193db7a6808cd
58 N5e945be52d814512a78193db7a6808cd rdf:first sg:person.013531324035.31
59 rdf:rest rdf:nil
60 N711e97a6357543aea59e6b7df71e0cb6 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N74dc3544419741849b7936a64e27735d rdf:first sg:person.013174232477.45
63 rdf:rest N78dbee11d7c6452d8bca054c30288512
64 N78dbee11d7c6452d8bca054c30288512 rdf:first sg:person.011052721431.97
65 rdf:rest Nf129826cbdea42f896d9d61dca1ac43c
66 N9bba94a88aa0413d9c71b22d049676d3 schema:name dimensions_id
67 schema:value pub.1009768313
68 rdf:type schema:PropertyValue
69 Naf05f30f6f6f4e7fbf6c3c48e7f34e38 schema:name doi
70 schema:value 10.1007/11533719_82
71 rdf:type schema:PropertyValue
72 Nba99847c7d5b49dc84ff3eabcf9fcf17 schema:isbn 978-3-540-28061-3
73 978-3-540-31806-4
74 schema:name Computing and Combinatorics
75 rdf:type schema:Book
77 rdf:rest rdf:nil
78 Nf129826cbdea42f896d9d61dca1ac43c rdf:first sg:person.07456026767.03
79 rdf:rest N5938d3ef8788456f9b936cf9aa00813d
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.011052721431.97 schema:affiliation grid-institutes:grid.47609.3c
87 schema:familyName Kloks
88 schema:givenName Ton
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052721431.97
90 rdf:type schema:Person
91 sg:person.012216324536.52 schema:affiliation grid-institutes:grid.47609.3c
92 schema:familyName Liu
93 schema:givenName Jiping
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012216324536.52
95 rdf:type schema:Person
96 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
97 schema:familyName Chang
98 schema:givenName Maw-Shang
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
100 rdf:type schema:Person
101 sg:person.013531324035.31 schema:affiliation grid-institutes:grid.260567.0
102 schema:familyName Peng
103 schema:givenName Sheng-Lung
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
105 rdf:type schema:Person
106 sg:person.07456026767.03 schema:affiliation grid-institutes:grid.29172.3f
107 schema:familyName Kratsch
108 schema:givenName Dieter
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07456026767.03
110 rdf:type schema:Person
111 grid-institutes:grid.260567.0 schema:alternateName Department of Computer Science and Information Engineering, National Dong Hwa University, 974, Hualien, Taiwan, R.O.C.
112 schema:name Department of Computer Science and Information Engineering, National Dong Hwa University, 974, Hualien, Taiwan, R.O.C.
113 rdf:type schema:Organization
114 grid-institutes:grid.29172.3f schema:alternateName LITA, Université de Metz, 57045, Metz Cedex 01, France
115 schema:name LITA, Université de Metz, 57045, Metz Cedex 01, France
116 rdf:type schema:Organization
117 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C.
118 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Chiayi, Taiwan, R.O.C.
119 rdf:type schema:Organization
120 grid-institutes:grid.47609.3c schema:alternateName Department of Mathematics and Computer Science, The university of Lethbridge, T1K 3M4, Alberta, Canada
121 schema:name Department of Mathematics and Computer Science, The university of Lethbridge, T1K 3M4, Alberta, Canada
122 rdf:type schema:Organization