# On Probe Permutation Graphs

Ontology type: schema:Chapter

### Chapter Info

DATE

2006

AUTHORS ABSTRACT

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 two sets ℙ, the probes, and ℕ, the nonprobes, where ℕ is an independent set, such that G can be embedded into 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 vertices of ℕ. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned 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}. In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity O(n2) where n is the number of vertices in the input graph. We show that there are at most O(n4) minimal separators for a probe permutation graph. As a consequence, there exist polynomial-time algorithms solving treewidth and minimum fill-in problems for probe permutation graphs. More... »

PAGES

494-504

### Book

TITLE

Theory and Applications of Models of Computation

ISBN

978-3-540-34021-8
978-3-540-34022-5

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11750321_47

DOI

http://dx.doi.org/10.1007/11750321_47

DIMENSIONS

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

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": "Institute of Mathematics, Academia Sinica, 11529, Nangang, Taipei, Taiwan",
"id": "http://www.grid.ac/institutes/grid.28665.3f",
"name": [
"Institute of Mathematics, Academia Sinica, 11529, Nangang, Taipei, Taiwan"
],
"type": "Organization"
},
"familyName": "Chandler",
"givenName": "David B.",
"id": "sg:person.015431467001.58",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015431467001.58"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"Department of Computer Science and Information Engineering, National Chung Cheng University, 62107, 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"
},
{
"affiliation": {
"alternateName": "Institute of Mathematics, Academia Sinica, 11529, Nangang, Taipei, Taiwan",
"id": "http://www.grid.ac/institutes/grid.28665.3f",
"name": [
"Institute of Mathematics, Academia Sinica, 11529, Nangang, Taipei, Taiwan"
],
"type": "Organization"
},
"familyName": "Kloks",
"givenName": "Antonius J. J.",
"id": "sg:person.012164374015.74",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012164374015.74"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics and Computer Science, University of Lethbridge, T1K 3M4, Alberta, Canada",
"id": "http://www.grid.ac/institutes/grid.47609.3c",
"name": [
"Department of Mathematics and Computer Science, 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, 97401, Hualien, Taiwan",
"id": "http://www.grid.ac/institutes/grid.260567.0",
"name": [
"Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Hualien, Taiwan"
],
"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": "2006",
"datePublishedReg": "2006-01-01",
"description": "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}$\\mathcal{G}$\\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}$\\mathcal{G}$\\end{document} if its vertices can be partitioned into two sets \u2119, the probes, and \u2115, the nonprobes, where \u2115 is an independent set, such that G can be embedded into 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}$\\mathcal{G}$\\end{document} by adding edges between certain vertices of \u2115. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned 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}$\\mathcal{G}$\\end{document}. In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity O(n2) where n is the number of vertices in the input graph. We show that there are at most O(n4) minimal separators for a probe permutation graph. As a consequence, there exist polynomial-time algorithms solving treewidth and minimum fill-in problems for probe permutation graphs.",
"editor": [
{
"familyName": "Cai",
"givenName": "Jin-Yi",
"type": "Person"
},
{
"familyName": "Cooper",
"givenName": "S. Barry",
"type": "Person"
},
{
"familyName": "Li",
"givenName": "Angsheng",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11750321_47",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-34021-8",
"978-3-540-34022-5"
],
"name": "Theory and Applications of Models of Computation",
"type": "Book"
},
"keywords": [
"probe permutation graphs",
"probe graphs",
"recognition algorithm",
"permutation graphs",
"time complexity",
"polynomial-time algorithm",
"class of graphs",
"graph",
"nonprobes",
"independent set",
"certain vertices",
"algorithm",
"number of vertices",
"input graph",
"minimal separators",
"minimum fill",
"graph G",
"vertices",
"set",
"partition",
"complexity",
"treewidth",
"class",
"edge",
"part",
"input",
"number",
"consequences",
"probe",
"separator",
"fill",
"problem",
"paper"
],
"name": "On Probe Permutation Graphs",
"pagination": "494-504",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1028752392"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11750321_47"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11750321_47",
"https://app.dimensions.ai/details/publication/pub.1028752392"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:51",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_238.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11750321_47"
}
]

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/11750321_47'

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/11750321_47'

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

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

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

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

140 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N5e5fb6cd49b94914ab02cb0a860b7feb
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description 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 two sets ℙ, the probes, and ℕ, the nonprobes, where ℕ is an independent set, such that G can be embedded into 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 vertices of ℕ. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned 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}. In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity O(n2) where n is the number of vertices in the input graph. We show that there are at most O(n4) minimal separators for a probe permutation graph. As a consequence, there exist polynomial-time algorithms solving treewidth and minimum fill-in problems for probe permutation graphs.
7 schema:editor Nc01724994e634a1b8823c25705f1979e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
12 schema:keywords algorithm
13 certain vertices
14 class
15 class of graphs
16 complexity
17 consequences
18 edge
19 fill
20 graph
21 graph G
22 independent set
23 input
24 input graph
25 minimal separators
26 minimum fill
27 nonprobes
28 number
29 number of vertices
30 paper
31 part
32 partition
33 permutation graphs
34 polynomial-time algorithm
35 probe
36 probe graphs
37 probe permutation graphs
38 problem
39 recognition algorithm
40 separator
41 set
42 time complexity
43 treewidth
44 vertices
45 schema:name On Probe Permutation Graphs
46 schema:pagination 494-504
47 schema:productId N60ce67bb692a4bd99bf0e779884ef6c2
48 Nec14051783d2418eaf0e7c346b8c40bc
49 schema:publisher N220d98c8965642469f002af5fe8d250e
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028752392
51 https://doi.org/10.1007/11750321_47
52 schema:sdDatePublished 2021-11-01T18:51
55 schema:url https://doi.org/10.1007/11750321_47
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N0788306c9fb340ca82c6c78d89e3013a rdf:first sg:person.013531324035.31
60 rdf:rest rdf:nil
61 N220d98c8965642469f002af5fe8d250e schema:name Springer Nature
62 rdf:type schema:Organisation
63 N36e5e5e15a8a4250b892dde53408defe schema:familyName Li
64 schema:givenName Angsheng
65 rdf:type schema:Person
66 N5e5fb6cd49b94914ab02cb0a860b7feb rdf:first sg:person.015431467001.58
67 rdf:rest Nd2d20bfb4d22495b9e3345e7a717bd6f
68 N60ce67bb692a4bd99bf0e779884ef6c2 schema:name doi
69 schema:value 10.1007/11750321_47
70 rdf:type schema:PropertyValue
72 rdf:rest N0788306c9fb340ca82c6c78d89e3013a
73 N76c2bc6c319249ac8dc00c9a51ea29e9 rdf:first N36e5e5e15a8a4250b892dde53408defe
74 rdf:rest rdf:nil
75 N7bb15eece8e741f390e95d6308f5f36a schema:familyName Cai
76 schema:givenName Jin-Yi
77 rdf:type schema:Person
78 Nc01724994e634a1b8823c25705f1979e rdf:first N7bb15eece8e741f390e95d6308f5f36a
79 rdf:rest Nc112ff0ba72b4b8e8dc8c6222c246937
80 Nc112ff0ba72b4b8e8dc8c6222c246937 rdf:first Nc37bf15dfe3844a4b61f6efde02f89af
81 rdf:rest N76c2bc6c319249ac8dc00c9a51ea29e9
82 Nc37bf15dfe3844a4b61f6efde02f89af schema:familyName Cooper
83 schema:givenName S. Barry
84 rdf:type schema:Person
85 Nc66834fe6746404e8dd1c317849a42d4 rdf:first sg:person.012164374015.74
87 Nd049b4b0b387482d928783b9d52342ad schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 Nd2d20bfb4d22495b9e3345e7a717bd6f rdf:first sg:person.013174232477.45
90 rdf:rest Nc66834fe6746404e8dd1c317849a42d4
91 Nec14051783d2418eaf0e7c346b8c40bc schema:name dimensions_id
92 schema:value pub.1028752392
93 rdf:type schema:PropertyValue
95 978-3-540-34022-5
96 schema:name Theory and Applications of Models of Computation
97 rdf:type schema:Book
98 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
99 schema:name Information and Computing Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
102 schema:name Computation Theory and Mathematics
103 rdf:type schema:DefinedTerm
104 sg:person.012164374015.74 schema:affiliation grid-institutes:grid.28665.3f
105 schema:familyName Kloks
106 schema:givenName Antonius J. J.
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012164374015.74
108 rdf:type schema:Person
109 sg:person.012216324536.52 schema:affiliation grid-institutes:grid.47609.3c
110 schema:familyName Liu
111 schema:givenName Jiping
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012216324536.52
113 rdf:type schema:Person
114 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
115 schema:familyName Chang
116 schema:givenName Maw-Shang
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
118 rdf:type schema:Person
119 sg:person.013531324035.31 schema:affiliation grid-institutes:grid.260567.0
120 schema:familyName Peng
121 schema:givenName Sheng-Lung
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
123 rdf:type schema:Person
124 sg:person.015431467001.58 schema:affiliation grid-institutes:grid.28665.3f
125 schema:familyName Chandler
126 schema:givenName David B.
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015431467001.58
128 rdf:type schema:Person
129 grid-institutes:grid.260567.0 schema:alternateName Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Hualien, Taiwan
130 schema:name Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Hualien, Taiwan
131 rdf:type schema:Organization
132 grid-institutes:grid.28665.3f schema:alternateName Institute of Mathematics, Academia Sinica, 11529, Nangang, Taipei, Taiwan
133 schema:name Institute of Mathematics, Academia Sinica, 11529, Nangang, Taipei, 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, 62107, Chiayi, Taiwan
136 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan
137 rdf:type schema:Organization
138 grid-institutes:grid.47609.3c schema:alternateName Department of Mathematics and Computer Science, University of Lethbridge, T1K 3M4, Alberta, Canada
139 schema:name Department of Mathematics and Computer Science, University of Lethbridge, T1K 3M4, Alberta, Canada
140 rdf:type schema:Organization