Deferred-query—An efficient approach for problems on interval and circular-arc graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1993

AUTHORS

Maw-Shang Chang , Sheng-Lung Peng , Jenn-Liang Liaw

ABSTRACT

An efficient approach, called deferred-query, is proposed in this paper to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit and matching problems on a set of sorted intervals. Using above results, the optimal path cover, hamiltonian path and hamiltonian circuit problems can also be solved in O(n) time on a set of sorted arcs. More... »

PAGES

222-233

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57155-8_250

DOI

http://dx.doi.org/10.1007/3-540-57155-8_250

DIMENSIONS

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


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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621"
          ], 
          "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 Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liaw", 
        "givenName": "Jenn-Liang", 
        "id": "sg:person.013003525275.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013003525275.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "An efficient approach, called deferred-query, is proposed in this paper to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit and matching problems on a set of sorted intervals. Using above results, the optimal path cover, hamiltonian path and hamiltonian circuit problems can also be solved in O(n) time on a set of sorted arcs.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Santoro", 
        "givenName": "Nicola", 
        "type": "Person"
      }, 
      {
        "familyName": "Whitesides", 
        "givenName": "Sue", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57155-8_250", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57155-1", 
        "978-3-540-47918-5"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "optimal path cover", 
      "Hamiltonian circuit problem", 
      "circular-arc graphs", 
      "efficient approach", 
      "Hamiltonian path", 
      "domatic partition", 
      "path cover", 
      "Hamiltonian circuits", 
      "set", 
      "algorithm", 
      "circuit problems", 
      "path", 
      "graph", 
      "partition", 
      "time", 
      "circuit", 
      "results", 
      "arc", 
      "intervals", 
      "cover", 
      "above results", 
      "problem", 
      "approach", 
      "paper", 
      "sorted intervals", 
      "sorted arcs"
    ], 
    "name": "Deferred-query\u2014An efficient approach for problems on interval and circular-arc graphs", 
    "pagination": "222-233", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041510827"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57155-8_250"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57155-8_250", 
      "https://app.dimensions.ai/details/publication/pub.1041510827"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_296.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-57155-8_250"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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/3-540-57155-8_250'

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/3-540-57155-8_250'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57155-8_250'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57155-8_250'


 

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

115 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57155-8_250 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N903fef7fd5334a9c8280494b5f855385
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 schema:description An efficient approach, called deferred-query, is proposed in this paper to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit and matching problems on a set of sorted intervals. Using above results, the optimal path cover, hamiltonian path and hamiltonian circuit problems can also be solved in O(n) time on a set of sorted arcs.
7 schema:editor N195b1650bd2642a3baae0b9359d87141
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8e222c787e9043d780d80f521408d94d
12 schema:keywords Hamiltonian circuit problem
13 Hamiltonian circuits
14 Hamiltonian path
15 above results
16 algorithm
17 approach
18 arc
19 circuit
20 circuit problems
21 circular-arc graphs
22 cover
23 domatic partition
24 efficient approach
25 graph
26 intervals
27 optimal path cover
28 paper
29 partition
30 path
31 path cover
32 problem
33 results
34 set
35 sorted arcs
36 sorted intervals
37 time
38 schema:name Deferred-query—An efficient approach for problems on interval and circular-arc graphs
39 schema:pagination 222-233
40 schema:productId Nb10a4f1c94754bffa42b89b8a9f8c3dc
41 Ned3b0a0b7bc246558f20f77ba7e9d935
42 schema:publisher Nd153e58382e348bda07f4aaeed37c3d7
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041510827
44 https://doi.org/10.1007/3-540-57155-8_250
45 schema:sdDatePublished 2021-11-01T18:54
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher Ne7d72b7aecb44905b112321ca9be4df3
48 schema:url https://doi.org/10.1007/3-540-57155-8_250
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N195b1650bd2642a3baae0b9359d87141 rdf:first N1c7cc1a2768649668cf308d8db7af6f9
53 rdf:rest Nce89c0e64dd9440b8ab01aa59bd2e346
54 N1c7cc1a2768649668cf308d8db7af6f9 schema:familyName Dehne
55 schema:givenName Frank
56 rdf:type schema:Person
57 N34f37a80948e4838955f518a13230c35 rdf:first sg:person.013531324035.31
58 rdf:rest N9eae4acbcef341deac80772ab81e710e
59 N752036aa3ef8440cbbf178f641c47e9d schema:familyName Whitesides
60 schema:givenName Sue
61 rdf:type schema:Person
62 N7d414da13e2b44d7a30ad4a11e023a90 rdf:first Necd2f89f621740a492f2f6eb239de5f9
63 rdf:rest Ncc5b3eb0949d4b9fb755cb519ffa6129
64 N8e222c787e9043d780d80f521408d94d schema:isbn 978-3-540-47918-5
65 978-3-540-57155-1
66 schema:name Algorithms and Data Structures
67 rdf:type schema:Book
68 N903fef7fd5334a9c8280494b5f855385 rdf:first sg:person.013174232477.45
69 rdf:rest N34f37a80948e4838955f518a13230c35
70 N9eae4acbcef341deac80772ab81e710e rdf:first sg:person.013003525275.52
71 rdf:rest rdf:nil
72 Na62f247a9abc46a082e3fcded1744be3 schema:familyName Sack
73 schema:givenName Jörg-Rüdiger
74 rdf:type schema:Person
75 Nb10a4f1c94754bffa42b89b8a9f8c3dc schema:name dimensions_id
76 schema:value pub.1041510827
77 rdf:type schema:PropertyValue
78 Ncc5b3eb0949d4b9fb755cb519ffa6129 rdf:first N752036aa3ef8440cbbf178f641c47e9d
79 rdf:rest rdf:nil
80 Nce89c0e64dd9440b8ab01aa59bd2e346 rdf:first Na62f247a9abc46a082e3fcded1744be3
81 rdf:rest N7d414da13e2b44d7a30ad4a11e023a90
82 Nd153e58382e348bda07f4aaeed37c3d7 schema:name Springer Nature
83 rdf:type schema:Organisation
84 Ne7d72b7aecb44905b112321ca9be4df3 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 Necd2f89f621740a492f2f6eb239de5f9 schema:familyName Santoro
87 schema:givenName Nicola
88 rdf:type schema:Person
89 Ned3b0a0b7bc246558f20f77ba7e9d935 schema:name doi
90 schema:value 10.1007/3-540-57155-8_250
91 rdf:type schema:PropertyValue
92 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
93 schema:name Mathematical Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
96 schema:name Numerical and Computational Mathematics
97 rdf:type schema:DefinedTerm
98 sg:person.013003525275.52 schema:affiliation grid-institutes:grid.412047.4
99 schema:familyName Liaw
100 schema:givenName Jenn-Liang
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013003525275.52
102 rdf:type schema:Person
103 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
104 schema:familyName Chang
105 schema:givenName Maw-Shang
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
107 rdf:type schema:Person
108 sg:person.013531324035.31 schema:affiliation grid-institutes:grid.412047.4
109 schema:familyName Peng
110 schema:givenName Sheng-Lung
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
112 rdf:type schema:Person
113 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621
114 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, Chiayi, Taiwan 621
115 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...