On some combinatorial problems in cographs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-02-25

AUTHORS

Harshita Kona, N. Sadagopan

ABSTRACT

The family of graphs that can be constructed from isolated vertices by disjoint union and graph join operations are called cographs. These graphs can be represented in a tree-like representation termed parse tree or cotree. In this paper, we study some popular combinatorial problems restricted to cographs. We first present a structural characterization of minimal vertex separators in cographs. Further, we show that listing all minimal vertex separators and finding some constrained vertex separators are linear-time solvable in cographs. We propose polynomial-time algorithms for some connectivity augmentation problems and its variants in cographs, preserving the cograph property. Finally, using the dynamic programming paradigm, we present a generic framework to solve classical optimization problems such as the longest path, the Steiner path and the minimum leaf spanning tree problems restricted to cographs and our framework yields polynomial-time algorithms for the three problems. More... »

PAGES

1-15

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s12572-019-00244-7

DOI

http://dx.doi.org/10.1007/s12572-019-00244-7

DIMENSIONS

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


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": {
          "name": [
            "Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kona", 
        "givenName": "Harshita", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sadagopan", 
        "givenName": "N.", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0166-218x(90)90083-o", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002944583"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(81)90013-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012596998"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-010-9411-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012699330", 
          "https://doi.org/10.1007/s00453-010-9411-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(89)90031-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014375645"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(87)90038-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021835807"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(93)90230-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029145902"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jctb.1995.1044", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029206840"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39890-5_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043423896", 
          "https://doi.org/10.1007/978-3-540-39890-5_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39890-5_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043423896", 
          "https://doi.org/10.1007/978-3-540-39890-5_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2007.02.010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045057680"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(00)00197-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050138705"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0205044", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841330"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0214065", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841854"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0405003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844697"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/100787507", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062858670"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/100793529", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062858855"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054113400054", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062897312"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.7155/jgaa.00377", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1073626663"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9780898719796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098557270"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-02-25", 
    "datePublishedReg": "2019-02-25", 
    "description": "The family of graphs that can be constructed from isolated vertices by disjoint union and graph join operations are called cographs. These graphs can be represented in a tree-like representation termed parse tree or cotree. In this paper, we study some popular combinatorial problems restricted to cographs. We first present a structural characterization of minimal vertex separators in cographs. Further, we show that listing all minimal vertex separators and finding some constrained vertex separators are linear-time solvable in cographs. We propose polynomial-time algorithms for some connectivity augmentation problems and its variants in cographs, preserving the cograph property. Finally, using the dynamic programming paradigm, we present a generic framework to solve classical optimization problems such as the longest path, the Steiner path and the minimum leaf spanning tree problems restricted to cographs and our framework yields polynomial-time algorithms for the three problems.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s12572-019-00244-7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1050051", 
        "issn": [
          "0975-0770", 
          "0975-5616"
        ], 
        "name": "International Journal of Advances in Engineering Sciences and Applied Mathematics", 
        "type": "Periodical"
      }
    ], 
    "name": "On some combinatorial problems in cographs", 
    "pagination": "1-15", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "93b8c8f0dd9d0c37fc287d86b9a4cc196db84d89a9c3768b56d2af157891637a"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s12572-019-00244-7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112364964"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s12572-019-00244-7", 
      "https://app.dimensions.ai/details/publication/pub.1112364964"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:57", 
    "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/0000000359_0000000359/records_29219_00000003.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs12572-019-00244-7"
  }
]
 

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/s12572-019-00244-7'

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/s12572-019-00244-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12572-019-00244-7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12572-019-00244-7'


 

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

117 TRIPLES      21 PREDICATES      42 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s12572-019-00244-7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8418fd2d12a44f15bdf5485ec2e11899
4 schema:citation sg:pub.10.1007/978-3-540-39890-5_11
5 sg:pub.10.1007/s00453-010-9411-3
6 https://doi.org/10.1006/jctb.1995.1044
7 https://doi.org/10.1016/0020-0190(93)90230-7
8 https://doi.org/10.1016/0022-0000(87)90038-9
9 https://doi.org/10.1016/0166-218x(81)90013-5
10 https://doi.org/10.1016/0166-218x(89)90031-0
11 https://doi.org/10.1016/0166-218x(90)90083-o
12 https://doi.org/10.1016/j.ipl.2007.02.010
13 https://doi.org/10.1016/s0166-218x(00)00197-9
14 https://doi.org/10.1137/0205044
15 https://doi.org/10.1137/0214065
16 https://doi.org/10.1137/0405003
17 https://doi.org/10.1137/1.9780898719796
18 https://doi.org/10.1137/100787507
19 https://doi.org/10.1137/100793529
20 https://doi.org/10.1142/s0129054113400054
21 https://doi.org/10.7155/jgaa.00377
22 schema:datePublished 2019-02-25
23 schema:datePublishedReg 2019-02-25
24 schema:description The family of graphs that can be constructed from isolated vertices by disjoint union and graph join operations are called cographs. These graphs can be represented in a tree-like representation termed parse tree or cotree. In this paper, we study some popular combinatorial problems restricted to cographs. We first present a structural characterization of minimal vertex separators in cographs. Further, we show that listing all minimal vertex separators and finding some constrained vertex separators are linear-time solvable in cographs. We propose polynomial-time algorithms for some connectivity augmentation problems and its variants in cographs, preserving the cograph property. Finally, using the dynamic programming paradigm, we present a generic framework to solve classical optimization problems such as the longest path, the Steiner path and the minimum leaf spanning tree problems restricted to cographs and our framework yields polynomial-time algorithms for the three problems.
25 schema:genre research_article
26 schema:inLanguage en
27 schema:isAccessibleForFree false
28 schema:isPartOf sg:journal.1050051
29 schema:name On some combinatorial problems in cographs
30 schema:pagination 1-15
31 schema:productId N142e09e140824a66a4ec2386334c175b
32 Na04ed9cf74a14985b2023710adaa5151
33 Na77a45abf80347ebb251a87b440e5f8c
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112364964
35 https://doi.org/10.1007/s12572-019-00244-7
36 schema:sdDatePublished 2019-04-11T11:57
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher Nf8a495b8d7744b1ea71256ea2ee6244f
39 schema:url https://link.springer.com/10.1007%2Fs12572-019-00244-7
40 sgo:license sg:explorer/license/
41 sgo:sdDataset articles
42 rdf:type schema:ScholarlyArticle
43 N142e09e140824a66a4ec2386334c175b schema:name doi
44 schema:value 10.1007/s12572-019-00244-7
45 rdf:type schema:PropertyValue
46 N7d1e1a778d5b4214980979c3c0d903a1 schema:name Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, Chennai, India
47 rdf:type schema:Organization
48 N8418fd2d12a44f15bdf5485ec2e11899 rdf:first N9e734ac9e4ae40e282369f79cc920a7e
49 rdf:rest Nbdeb368ebb864304a415f1f0d7c55cf3
50 N9e734ac9e4ae40e282369f79cc920a7e schema:affiliation Ne7756ec9ed8046ae8c150ca12e956d77
51 schema:familyName Kona
52 schema:givenName Harshita
53 rdf:type schema:Person
54 Na04ed9cf74a14985b2023710adaa5151 schema:name dimensions_id
55 schema:value pub.1112364964
56 rdf:type schema:PropertyValue
57 Na77a45abf80347ebb251a87b440e5f8c schema:name readcube_id
58 schema:value 93b8c8f0dd9d0c37fc287d86b9a4cc196db84d89a9c3768b56d2af157891637a
59 rdf:type schema:PropertyValue
60 Nbdeb368ebb864304a415f1f0d7c55cf3 rdf:first Nec6137f14b0e4ae284f7a1847dd6b5ec
61 rdf:rest rdf:nil
62 Ne7756ec9ed8046ae8c150ca12e956d77 schema:name Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, Chennai, India
63 rdf:type schema:Organization
64 Nec6137f14b0e4ae284f7a1847dd6b5ec schema:affiliation N7d1e1a778d5b4214980979c3c0d903a1
65 schema:familyName Sadagopan
66 schema:givenName N.
67 rdf:type schema:Person
68 Nf8a495b8d7744b1ea71256ea2ee6244f schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
71 schema:name Information and Computing Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
74 schema:name Computation Theory and Mathematics
75 rdf:type schema:DefinedTerm
76 sg:journal.1050051 schema:issn 0975-0770
77 0975-5616
78 schema:name International Journal of Advances in Engineering Sciences and Applied Mathematics
79 rdf:type schema:Periodical
80 sg:pub.10.1007/978-3-540-39890-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043423896
81 https://doi.org/10.1007/978-3-540-39890-5_11
82 rdf:type schema:CreativeWork
83 sg:pub.10.1007/s00453-010-9411-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012699330
84 https://doi.org/10.1007/s00453-010-9411-3
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1006/jctb.1995.1044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029206840
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1016/0020-0190(93)90230-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029145902
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1016/0022-0000(87)90038-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021835807
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/0166-218x(81)90013-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012596998
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0166-218x(89)90031-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014375645
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/0166-218x(90)90083-o schema:sameAs https://app.dimensions.ai/details/publication/pub.1002944583
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/j.ipl.2007.02.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045057680
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/s0166-218x(00)00197-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050138705
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1137/0205044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841330
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1137/0214065 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841854
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1137/0405003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844697
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1137/1.9780898719796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557270
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1137/100787507 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062858670
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1137/100793529 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062858855
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1142/s0129054113400054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897312
115 rdf:type schema:CreativeWork
116 https://doi.org/10.7155/jgaa.00377 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073626663
117 rdf:type schema:CreativeWork
 




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


...