On the complete width and edge clique cover problems View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-08

AUTHORS

Van Bang Le, Sheng-Lung Peng

ABSTRACT

A complete graph is the graph in which every two vertices are adjacent. For a graph G=(V,E), the complete width of G is the minimum k such that there exist k independent sets Ni⊆V, 1≤i≤k, such that the graph G′ obtained from G by adding some new edges between certain vertices inside the sets Ni, 1≤i≤k, is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on 3K2-free bipartite graphs and polynomially solvable on 2K2-free bipartite graphs and on (2K2,C4)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on 3K2¯-free co-bipartite graphs and polynomially solvable on C4-free co-bipartite graphs and on (2K2,C4)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most 2k vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most 2k vertices. Finally we determine all graphs of small complete width k≤3. More... »

PAGES

532-548

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10878-016-0106-9

DOI

http://dx.doi.org/10.1007/s10878-016-0106-9

DIMENSIONS

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


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": "University of Rostock", 
          "id": "https://www.grid.ac/institutes/grid.10493.3f", 
          "name": [
            "Institut F\u00fcr Informatik, Universit\u00e4t Rostock, Rostock, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Le", 
        "givenName": "Van Bang", 
        "id": "sg:person.011311256712.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011311256712.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Dong Hwa University", 
          "id": "https://www.grid.ac/institutes/grid.260567.0", 
          "name": [
            "Department of Computer Science and Information Engineering, National Dong Hwa University, 974, Hualien, Taiwan"
          ], 
          "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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/1412228.1412236", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000622368"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2014.12.014", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001647315"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2014.12.014", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001647315"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(91)90165-e", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004572818"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1004947649", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21275-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004947649", 
          "https://doi.org/10.1007/978-3-319-21275-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21275-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004947649", 
          "https://doi.org/10.1007/978-3-319-21275-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/1385-7258(77)90055-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009535078"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(94)00022-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010395177"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-70575-8_52", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010918995", 
          "https://doi.org/10.1007/978-3-540-70575-8_52"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21398-9_42", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015369688", 
          "https://doi.org/10.1007/978-3-319-21398-9_42"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2010.10.041", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018941657"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2010.10.041", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018941657"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2010.10.041", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018941657"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(93)90477-b", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027177987"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/359340.359346", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032805424"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(94)00350-r", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038317738"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(90)90092-q", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049270783"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2594439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049986052"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.cosrev.2010.01.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052196555"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0210022", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841575"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0210054", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841607"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0213005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841739"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973105.75", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801684"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9780898719796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098557270"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511542985", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098786938"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-08", 
    "datePublishedReg": "2018-08-01", 
    "description": "A complete graph is the graph in which every two vertices are adjacent. For a graph G=(V,E), the complete width of G is the minimum k such that there exist k independent sets Ni\u2286V, 1\u2264i\u2264k, such that the graph G\u2032 obtained from G by adding some new edges between certain vertices inside the sets Ni, 1\u2264i\u2264k, is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on 3K2-free bipartite graphs and polynomially solvable on 2K2-free bipartite graphs and on (2K2,C4)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on 3K2\u00af-free co-bipartite graphs and polynomially solvable on C4-free co-bipartite graphs and on (2K2,C4)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most 2k vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most 2k vertices. Finally we determine all graphs of small complete width k\u22643.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10878-016-0106-9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1036683", 
        "issn": [
          "1382-6905", 
          "1573-2886"
        ], 
        "name": "Journal of Combinatorial Optimization", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "36"
      }
    ], 
    "name": "On the complete width and edge clique cover problems", 
    "pagination": "532-548", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "dcf1de09abb7a8f6fac11ddc2e7126628c1a28d16d8667d480b1b2354d3b7649"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10878-016-0106-9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046382612"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10878-016-0106-9", 
      "https://app.dimensions.ai/details/publication/pub.1046382612"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:39", 
    "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/0000000363_0000000363/records_70046_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10878-016-0106-9"
  }
]
 

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/s10878-016-0106-9'

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/s10878-016-0106-9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-016-0106-9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-016-0106-9'


 

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

139 TRIPLES      21 PREDICATES      49 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10878-016-0106-9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nda36ad874580468e865d28ca069a0078
4 schema:citation sg:pub.10.1007/978-3-319-21275-3
5 sg:pub.10.1007/978-3-319-21398-9_42
6 sg:pub.10.1007/978-3-540-70575-8_52
7 https://app.dimensions.ai/details/publication/pub.1004947649
8 https://doi.org/10.1016/0012-365x(93)90477-b
9 https://doi.org/10.1016/0012-365x(94)00350-r
10 https://doi.org/10.1016/0020-0190(91)90165-e
11 https://doi.org/10.1016/0166-218x(90)90092-q
12 https://doi.org/10.1016/0166-218x(94)00022-0
13 https://doi.org/10.1016/1385-7258(77)90055-5
14 https://doi.org/10.1016/j.cosrev.2010.01.001
15 https://doi.org/10.1016/j.tcs.2010.10.041
16 https://doi.org/10.1016/j.tcs.2014.12.014
17 https://doi.org/10.1017/cbo9780511542985
18 https://doi.org/10.1137/0210022
19 https://doi.org/10.1137/0210054
20 https://doi.org/10.1137/0213005
21 https://doi.org/10.1137/1.9780898719796
22 https://doi.org/10.1137/1.9781611973105.75
23 https://doi.org/10.1145/1412228.1412236
24 https://doi.org/10.1145/2594439
25 https://doi.org/10.1145/359340.359346
26 schema:datePublished 2018-08
27 schema:datePublishedReg 2018-08-01
28 schema:description A complete graph is the graph in which every two vertices are adjacent. For a graph G=(V,E), the complete width of G is the minimum k such that there exist k independent sets Ni⊆V, 1≤i≤k, such that the graph G′ obtained from G by adding some new edges between certain vertices inside the sets Ni, 1≤i≤k, is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on 3K2-free bipartite graphs and polynomially solvable on 2K2-free bipartite graphs and on (2K2,C4)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on 3K2¯-free co-bipartite graphs and polynomially solvable on C4-free co-bipartite graphs and on (2K2,C4)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most 2k vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most 2k vertices. Finally we determine all graphs of small complete width k≤3.
29 schema:genre research_article
30 schema:inLanguage en
31 schema:isAccessibleForFree true
32 schema:isPartOf N4b7ce0b605934a4fb88a59e08de9487b
33 N8d9ccee1cd5345b4bea1dae92c6fd84e
34 sg:journal.1036683
35 schema:name On the complete width and edge clique cover problems
36 schema:pagination 532-548
37 schema:productId N108b4e6094e34537b436cbe32f99eac7
38 N33273f6c568f4c438f7e8df34df0c726
39 N7568d32a19984afa94032869fb978995
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046382612
41 https://doi.org/10.1007/s10878-016-0106-9
42 schema:sdDatePublished 2019-04-11T12:39
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Nc1083b8ae4314623a931862477703009
45 schema:url https://link.springer.com/10.1007%2Fs10878-016-0106-9
46 sgo:license sg:explorer/license/
47 sgo:sdDataset articles
48 rdf:type schema:ScholarlyArticle
49 N108b4e6094e34537b436cbe32f99eac7 schema:name readcube_id
50 schema:value dcf1de09abb7a8f6fac11ddc2e7126628c1a28d16d8667d480b1b2354d3b7649
51 rdf:type schema:PropertyValue
52 N33273f6c568f4c438f7e8df34df0c726 schema:name dimensions_id
53 schema:value pub.1046382612
54 rdf:type schema:PropertyValue
55 N4b7ce0b605934a4fb88a59e08de9487b schema:volumeNumber 36
56 rdf:type schema:PublicationVolume
57 N7568d32a19984afa94032869fb978995 schema:name doi
58 schema:value 10.1007/s10878-016-0106-9
59 rdf:type schema:PropertyValue
60 N8d9ccee1cd5345b4bea1dae92c6fd84e schema:issueNumber 2
61 rdf:type schema:PublicationIssue
62 Nc1083b8ae4314623a931862477703009 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 Nda36ad874580468e865d28ca069a0078 rdf:first sg:person.011311256712.11
65 rdf:rest Nf4cb91e1a5534a5b990bbcb2af252ee9
66 Nf4cb91e1a5534a5b990bbcb2af252ee9 rdf:first sg:person.013531324035.31
67 rdf:rest rdf:nil
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computation Theory and Mathematics
73 rdf:type schema:DefinedTerm
74 sg:journal.1036683 schema:issn 1382-6905
75 1573-2886
76 schema:name Journal of Combinatorial Optimization
77 rdf:type schema:Periodical
78 sg:person.011311256712.11 schema:affiliation https://www.grid.ac/institutes/grid.10493.3f
79 schema:familyName Le
80 schema:givenName Van Bang
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011311256712.11
82 rdf:type schema:Person
83 sg:person.013531324035.31 schema:affiliation https://www.grid.ac/institutes/grid.260567.0
84 schema:familyName Peng
85 schema:givenName Sheng-Lung
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
87 rdf:type schema:Person
88 sg:pub.10.1007/978-3-319-21275-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004947649
89 https://doi.org/10.1007/978-3-319-21275-3
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/978-3-319-21398-9_42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015369688
92 https://doi.org/10.1007/978-3-319-21398-9_42
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/978-3-540-70575-8_52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010918995
95 https://doi.org/10.1007/978-3-540-70575-8_52
96 rdf:type schema:CreativeWork
97 https://app.dimensions.ai/details/publication/pub.1004947649 schema:CreativeWork
98 https://doi.org/10.1016/0012-365x(93)90477-b schema:sameAs https://app.dimensions.ai/details/publication/pub.1027177987
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/0012-365x(94)00350-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1038317738
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/0020-0190(91)90165-e schema:sameAs https://app.dimensions.ai/details/publication/pub.1004572818
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0166-218x(90)90092-q schema:sameAs https://app.dimensions.ai/details/publication/pub.1049270783
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/0166-218x(94)00022-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010395177
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/1385-7258(77)90055-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009535078
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/j.cosrev.2010.01.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052196555
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/j.tcs.2010.10.041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018941657
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/j.tcs.2014.12.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001647315
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1017/cbo9780511542985 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098786938
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1137/0210022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841575
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/0210054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841607
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/0213005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841739
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1137/1.9780898719796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557270
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1137/1.9781611973105.75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801684
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/1412228.1412236 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000622368
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/2594439 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049986052
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/359340.359346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032805424
133 rdf:type schema:CreativeWork
134 https://www.grid.ac/institutes/grid.10493.3f schema:alternateName University of Rostock
135 schema:name Institut Für Informatik, Universität Rostock, Rostock, Germany
136 rdf:type schema:Organization
137 https://www.grid.ac/institutes/grid.260567.0 schema:alternateName National Dong Hwa University
138 schema:name Department of Computer Science and Information Engineering, National Dong Hwa University, 974, Hualien, Taiwan
139 rdf:type schema:Organization
 




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


...