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


...