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 Nbf0c409397fa48e3b3b49f53950be3a0
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 N074f0fc8617145b5b57268d378625daf
23 N0e0bab72b6c04b71a05e5a6655e35354
24 sg:journal.1047644
25 schema:name AnO(n3) recognition algorithm for bithreshold graphs
26 schema:pagination 416-425
27 schema:productId N065608ab4f924bd4a3a0d178a7f295aa
28 N673e34d50e0f4281baf0cda53474ecf2
29 Nee76866a4b3d49f3bc9846aa94cbcd3d
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 Nc4e30f77f5c746cfbdd73e715be6d0b6
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 N065608ab4f924bd4a3a0d178a7f295aa schema:name readcube_id
40 schema:value f378bd2be94360a3bacf280d79dfdca2bebe37851b090f86ae1551a28e4df7b1
41 rdf:type schema:PropertyValue
42 N074f0fc8617145b5b57268d378625daf schema:issueNumber 4
43 rdf:type schema:PublicationIssue
44 N0e0bab72b6c04b71a05e5a6655e35354 schema:volumeNumber 17
45 rdf:type schema:PublicationVolume
46 N673e34d50e0f4281baf0cda53474ecf2 schema:name doi
47 schema:value 10.1007/bf02523681
48 rdf:type schema:PropertyValue
49 N6dea4fc5dd274997b5c5cfffb3389ab8 rdf:first sg:person.011402427702.78
50 rdf:rest N6e5de004667a4d96950fcd4dfa5a5a6d
51 N6e5de004667a4d96950fcd4dfa5a5a6d rdf:first sg:person.010065200346.76
52 rdf:rest rdf:nil
53 Nbf0c409397fa48e3b3b49f53950be3a0 rdf:first sg:person.011034112477.54
54 rdf:rest N6dea4fc5dd274997b5c5cfffb3389ab8
55 Nc4e30f77f5c746cfbdd73e715be6d0b6 schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 Nee76866a4b3d49f3bc9846aa94cbcd3d schema:name dimensions_id
58 schema:value pub.1051110606
59 rdf:type schema:PropertyValue
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)


...