On the Min-Max 2-Cluster Editing Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Li-Hsuan Chen , Maw-Shang Chang , Chun-Chieh Wang , Bang Ye Wu

ABSTRACT

In this paper, we study the problem Min-Max 2-Cluster Editing which asks for a modification of a given graph into two maximal cliques by inserting or deleting edges such that the maximum number k of the editing edges incident to any vertex is minimized. We show the NP-hardness of the problem and present a polynomial-time algorithm when k < n/4, in which n is number of vertices. In addition, we design a 2-approximation algorithm and a branching algorithm for finding an optimal solution. By experiments on random graphs, we show that the exact algorithm is much more efficient than a trivial one. More... »

PAGES

133-142

Book

TITLE

Advances in Intelligent Systems and Applications - Volume 1

ISBN

978-3-642-35451-9
978-3-642-35452-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-35452-6_16

DOI

http://dx.doi.org/10.1007/978-3-642-35452-6_16

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Li-Hsuan", 
        "id": "sg:person.014055212561.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Hungkung University, 433, Taichung, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Hungkung University, 433, Taichung, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "Maw-Shang", 
        "id": "sg:person.013174232477.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Chun-Chieh", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "In this paper, we study the problem Min-Max 2-Cluster Editing which asks for a modification of a given graph into two maximal cliques by inserting or deleting edges such that the maximum number k of the editing edges incident to any vertex is minimized. We show the NP-hardness of the problem and present a polynomial-time algorithm when k\u2009<\u2009n/4, in which n is number of vertices. In addition, we design a 2-approximation algorithm and a branching algorithm for finding an optimal solution. By experiments on random graphs, we show that the exact algorithm is much more efficient than a trivial one.", 
    "editor": [
      {
        "familyName": "Chang", 
        "givenName": "Ruay-Shiung", 
        "type": "Person"
      }, 
      {
        "familyName": "Jain", 
        "givenName": "Lakhmi C.", 
        "type": "Person"
      }, 
      {
        "familyName": "Peng", 
        "givenName": "Sheng-Lung", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-35452-6_16", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-35451-9", 
        "978-3-642-35452-6"
      ], 
      "name": "Advances in Intelligent Systems and Applications - Volume 1", 
      "type": "Book"
    }, 
    "keywords": [
      "NP-hardness", 
      "polynomial-time algorithm", 
      "optimal solution", 
      "random graphs", 
      "number of vertices", 
      "exact algorithm", 
      "maximal cliques", 
      "branching algorithm", 
      "algorithm", 
      "trivial one", 
      "number k", 
      "graph", 
      "problem", 
      "edges incident", 
      "vertices", 
      "Editing problem", 
      "cliques", 
      "maximum number k", 
      "solution", 
      "n/4", 
      "one", 
      "number", 
      "edge", 
      "editing", 
      "experiments", 
      "modification", 
      "addition", 
      "incidents", 
      "paper", 
      "problem Min-Max 2-Cluster Editing", 
      "Min-Max 2-Cluster Editing", 
      "Min-Max 2-Cluster Editing Problem"
    ], 
    "name": "On the Min-Max 2-Cluster Editing Problem", 
    "pagination": "133-142", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032367522"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-35452-6_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-35452-6_16", 
      "https://app.dimensions.ai/details/publication/pub.1032367522"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_79.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-35452-6_16"
  }
]
 

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/978-3-642-35452-6_16'

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/978-3-642-35452-6_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-35452-6_16'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-35452-6_16'


 

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

125 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-35452-6_16 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N86d55eccbefb4e1ca98bdcb0474de5d7
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description In this paper, we study the problem Min-Max 2-Cluster Editing which asks for a modification of a given graph into two maximal cliques by inserting or deleting edges such that the maximum number k of the editing edges incident to any vertex is minimized. We show the NP-hardness of the problem and present a polynomial-time algorithm when k < n/4, in which n is number of vertices. In addition, we design a 2-approximation algorithm and a branching algorithm for finding an optimal solution. By experiments on random graphs, we show that the exact algorithm is much more efficient than a trivial one.
7 schema:editor N1e60cbfe054a4689a333bef6f53451b1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N65140d9cd44943f1a91f997e6dbd8945
12 schema:keywords Editing problem
13 Min-Max 2-Cluster Editing
14 Min-Max 2-Cluster Editing Problem
15 NP-hardness
16 addition
17 algorithm
18 branching algorithm
19 cliques
20 edge
21 edges incident
22 editing
23 exact algorithm
24 experiments
25 graph
26 incidents
27 maximal cliques
28 maximum number k
29 modification
30 n/4
31 number
32 number k
33 number of vertices
34 one
35 optimal solution
36 paper
37 polynomial-time algorithm
38 problem
39 problem Min-Max 2-Cluster Editing
40 random graphs
41 solution
42 trivial one
43 vertices
44 schema:name On the Min-Max 2-Cluster Editing Problem
45 schema:pagination 133-142
46 schema:productId N6038a382eab4463d9941409f92344dd0
47 Ne335f82ac5ac466581cbc6ed87baa8ae
48 schema:publisher N8d6287eaf1834a81a1dfe14ba5d60951
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032367522
50 https://doi.org/10.1007/978-3-642-35452-6_16
51 schema:sdDatePublished 2021-11-01T19:02
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N8170f99035834cc58dd0eca42d0fed18
54 schema:url https://doi.org/10.1007/978-3-642-35452-6_16
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N00e1d08e70c54f459a424aa2c7ba1b0a rdf:first Nf169078f5b0144388c1a59ff45e1edbe
59 rdf:rest rdf:nil
60 N1e60cbfe054a4689a333bef6f53451b1 rdf:first N3c1e611c36f34b3591a5a86c5f168d67
61 rdf:rest N4fa5b174819d4086b48ac0eddc1082b4
62 N3c1e611c36f34b3591a5a86c5f168d67 schema:familyName Chang
63 schema:givenName Ruay-Shiung
64 rdf:type schema:Person
65 N4fa5b174819d4086b48ac0eddc1082b4 rdf:first Nb123e38917614c958b107af20de7504a
66 rdf:rest N00e1d08e70c54f459a424aa2c7ba1b0a
67 N6038a382eab4463d9941409f92344dd0 schema:name dimensions_id
68 schema:value pub.1032367522
69 rdf:type schema:PropertyValue
70 N65140d9cd44943f1a91f997e6dbd8945 schema:isbn 978-3-642-35451-9
71 978-3-642-35452-6
72 schema:name Advances in Intelligent Systems and Applications - Volume 1
73 rdf:type schema:Book
74 N8170f99035834cc58dd0eca42d0fed18 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N86d55eccbefb4e1ca98bdcb0474de5d7 rdf:first sg:person.014055212561.22
77 rdf:rest Na6241e80dcad4f61b4817aee33b1a3b3
78 N8d6287eaf1834a81a1dfe14ba5d60951 schema:name Springer Nature
79 rdf:type schema:Organisation
80 Na0571b07743640ad96ab3b3b80be56c9 rdf:first Naca8775344f541e28f2ec12f6a6c9b3e
81 rdf:rest Ne6925d34816747e0b02b429b1393d816
82 Na6241e80dcad4f61b4817aee33b1a3b3 rdf:first sg:person.013174232477.45
83 rdf:rest Na0571b07743640ad96ab3b3b80be56c9
84 Naca8775344f541e28f2ec12f6a6c9b3e schema:affiliation grid-institutes:grid.412047.4
85 schema:familyName Wang
86 schema:givenName Chun-Chieh
87 rdf:type schema:Person
88 Nb123e38917614c958b107af20de7504a schema:familyName Jain
89 schema:givenName Lakhmi C.
90 rdf:type schema:Person
91 Ne335f82ac5ac466581cbc6ed87baa8ae schema:name doi
92 schema:value 10.1007/978-3-642-35452-6_16
93 rdf:type schema:PropertyValue
94 Ne6925d34816747e0b02b429b1393d816 rdf:first sg:person.013045767237.23
95 rdf:rest rdf:nil
96 Nf169078f5b0144388c1a59ff45e1edbe schema:familyName Peng
97 schema:givenName Sheng-Lung
98 rdf:type schema:Person
99 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
100 schema:name Mathematical Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
103 schema:name Numerical and Computational Mathematics
104 rdf:type schema:DefinedTerm
105 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
106 schema:familyName Wu
107 schema:givenName Bang Ye
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
109 rdf:type schema:Person
110 sg:person.013174232477.45 schema:affiliation grid-institutes:None
111 schema:familyName Chang
112 schema:givenName Maw-Shang
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
114 rdf:type schema:Person
115 sg:person.014055212561.22 schema:affiliation grid-institutes:grid.412047.4
116 schema:familyName Chen
117 schema:givenName Li-Hsuan
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22
119 rdf:type schema:Person
120 grid-institutes:None schema:alternateName Hungkung University, 433, Taichung, Taiwan, R.O.C.
121 schema:name Hungkung University, 433, Taichung, Taiwan, R.O.C.
122 rdf:type schema:Organization
123 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
124 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
125 rdf:type schema:Organization
 




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


...