AnO(n3) recognition algorithm for bithreshold graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1997-04

AUTHORS

S. De Agostino, R. Petreschi, A. Sterbini

ABSTRACT

A bithreshold graph is the edge intersection of two threshold graphs such that every independent set is independent in at least one of the threshold components. Recognizing a bithreshold graph is polynomially equivalent to recognizing its complement, i.e., a cobithreshold graph. In this paper we introduce a coloring of the vertices and of the edges of a cobithreshold graph that leads to a recognition and decomposition algorithm. This algorithm works inO(n3) time improving the previously knownO(n4) result [HM]. More... »

PAGES

416-425

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02523681

DOI

http://dx.doi.org/10.1007/bf02523681

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Computer Science, University \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "De Agostino", 
        "givenName": "S.", 
        "id": "sg:person.011034112477.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011034112477.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Computer Science, University \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Petreschi", 
        "givenName": "R.", 
        "id": "sg:person.011402427702.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Computer Science, University \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sterbini", 
        "givenName": "A.", 
        "id": "sg:person.010065200346.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010065200346.76"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70749-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015050349"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230190103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018279712"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(95)00030-g", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020700006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(93)90118-d", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022124325"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-0208(08)73469-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043843490"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70731-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046754752"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0206008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841347"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0218010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842109"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0603036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848761"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0605055", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848895"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0606049", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848947"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054192000036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062897591"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1997-04", 
    "datePublishedReg": "1997-04-01", 
    "description": "A bithreshold graph is the edge intersection of two threshold graphs such that every independent set is independent in at least one of the threshold components. Recognizing a bithreshold graph is polynomially equivalent to recognizing its complement, i.e., a cobithreshold graph. In this paper we introduce a coloring of the vertices and of the edges of a cobithreshold graph that leads to a recognition and decomposition algorithm. This algorithm works inO(n3) time improving the previously knownO(n4) result [HM].", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02523681", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "17"
      }
    ], 
    "name": "AnO(n3) recognition algorithm for bithreshold graphs", 
    "pagination": "416-425", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f378bd2be94360a3bacf280d79dfdca2bebe37851b090f86ae1551a28e4df7b1"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02523681"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051110606"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02523681", 
      "https://app.dimensions.ai/details/publication/pub.1051110606"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T15:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8663_00000508.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02523681"
  }
]
 

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/bf02523681'

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/bf02523681'

Turtle is a human-readable linked data format.

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

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

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


 

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

111 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02523681 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd6cb743c0ff447d4b88b705abd3758dd
4 schema:citation https://doi.org/10.1002/net.3230190103
5 https://doi.org/10.1016/0012-365x(93)90118-d
6 https://doi.org/10.1016/0020-0190(95)00030-g
7 https://doi.org/10.1016/s0167-5060(08)70731-3
8 https://doi.org/10.1016/s0167-5060(08)70749-0
9 https://doi.org/10.1016/s0304-0208(08)73469-8
10 https://doi.org/10.1137/0206008
11 https://doi.org/10.1137/0218010
12 https://doi.org/10.1137/0603036
13 https://doi.org/10.1137/0605055
14 https://doi.org/10.1137/0606049
15 https://doi.org/10.1142/s0129054192000036
16 schema:datePublished 1997-04
17 schema:datePublishedReg 1997-04-01
18 schema:description A bithreshold graph is the edge intersection of two threshold graphs such that every independent set is independent in at least one of the threshold components. Recognizing a bithreshold graph is polynomially equivalent to recognizing its complement, i.e., a cobithreshold graph. In this paper we introduce a coloring of the vertices and of the edges of a cobithreshold graph that leads to a recognition and decomposition algorithm. This algorithm works inO(n3) time improving the previously knownO(n4) result [HM].
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf N00cb9827868b442b90a7fca9e84458d2
23 N18e2d364dae64bfd9d5f2a5e4171c8f1
24 sg:journal.1047644
25 schema:name AnO(n3) recognition algorithm for bithreshold graphs
26 schema:pagination 416-425
27 schema:productId N664852b820a7489384471ccd2bcc355e
28 N6d1f72eb281f4eac98be4b7dd8947f3d
29 N6e64e0a0565a4348a2b969d22500af7a
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051110606
31 https://doi.org/10.1007/bf02523681
32 schema:sdDatePublished 2019-04-10T15:00
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N24482ee38684487f816c44004e11f79d
35 schema:url http://link.springer.com/10.1007%2FBF02523681
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N00cb9827868b442b90a7fca9e84458d2 schema:issueNumber 4
40 rdf:type schema:PublicationIssue
41 N18e2d364dae64bfd9d5f2a5e4171c8f1 schema:volumeNumber 17
42 rdf:type schema:PublicationVolume
43 N24482ee38684487f816c44004e11f79d schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 N664852b820a7489384471ccd2bcc355e schema:name readcube_id
46 schema:value f378bd2be94360a3bacf280d79dfdca2bebe37851b090f86ae1551a28e4df7b1
47 rdf:type schema:PropertyValue
48 N6d1f72eb281f4eac98be4b7dd8947f3d schema:name dimensions_id
49 schema:value pub.1051110606
50 rdf:type schema:PropertyValue
51 N6e64e0a0565a4348a2b969d22500af7a schema:name doi
52 schema:value 10.1007/bf02523681
53 rdf:type schema:PropertyValue
54 N9a41ad72f3ca45d59aca2793df6690ed rdf:first sg:person.011402427702.78
55 rdf:rest Nd183d636235645b2918c85ce567a4d48
56 Nd183d636235645b2918c85ce567a4d48 rdf:first sg:person.010065200346.76
57 rdf:rest rdf:nil
58 Nd6cb743c0ff447d4b88b705abd3758dd rdf:first sg:person.011034112477.54
59 rdf:rest N9a41ad72f3ca45d59aca2793df6690ed
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
64 schema:name Computation Theory and Mathematics
65 rdf:type schema:DefinedTerm
66 sg:journal.1047644 schema:issn 0178-4617
67 1432-0541
68 schema:name Algorithmica
69 rdf:type schema:Periodical
70 sg:person.010065200346.76 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
71 schema:familyName Sterbini
72 schema:givenName A.
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010065200346.76
74 rdf:type schema:Person
75 sg:person.011034112477.54 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
76 schema:familyName De Agostino
77 schema:givenName S.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011034112477.54
79 rdf:type schema:Person
80 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
81 schema:familyName Petreschi
82 schema:givenName R.
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
84 rdf:type schema:Person
85 https://doi.org/10.1002/net.3230190103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018279712
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1016/0012-365x(93)90118-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1022124325
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1016/0020-0190(95)00030-g schema:sameAs https://app.dimensions.ai/details/publication/pub.1020700006
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1016/s0167-5060(08)70731-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046754752
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/s0167-5060(08)70749-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015050349
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/s0304-0208(08)73469-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043843490
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1137/0206008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841347
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1137/0218010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842109
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1137/0603036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848761
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1137/0605055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848895
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1137/0606049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848947
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1142/s0129054192000036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897591
108 rdf:type schema:CreativeWork
109 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
110 schema:name Department of Computer Science, University “La Sapienza”, Via Salaria 113, 00198, Rome, Italy
111 rdf:type schema:Organization
 




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


...