Parameterized algorithms for min–max 2-cluster editing View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-07-19

AUTHORS

Li-Hsuan Chen, Bang Ye Wu

ABSTRACT

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for t More... »

PAGES

47-63

References to SciGraph publications

  • 2009. Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms in PARAMETERIZED AND EXACT COMPUTATION
  • 2014. On the Clique Editing Problem in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2014
  • 2014-02-07. Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions in ALGORITHMICA
  • 2004-03-19. Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems in ALGORITHMICA
  • 2005-01-28. Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation in THEORY OF COMPUTING SYSTEMS
  • 2008-07-16. Fixed-Parameter Enumerability of Cluster Editing and Related Problems in THEORY OF COMPUTING SYSTEMS
  • 2008-10-15. Fixed-Parameter Algorithms for Cluster Vertex Deletion in THEORY OF COMPUTING SYSTEMS
  • 2004-07. Correlation Clustering in MACHINE LEARNING
  • 2013. On the Min-Max 2-Cluster Editing Problem in ADVANCES IN INTELLIGENT SYSTEMS AND APPLICATIONS - VOLUME 1
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-016-0059-z

    DOI

    http://dx.doi.org/10.1007/s10878-016-0059-z

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "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, ROC", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
              ], 
              "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": "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-662-44465-8_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044291945", 
              "https://doi.org/10.1007/978-3-662-44465-8_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-014-9874-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051438401", 
              "https://doi.org/10.1007/s00453-014-9874-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11269-0_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022401414", 
              "https://doi.org/10.1007/978-3-642-11269-0_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-004-1090-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051624082", 
              "https://doi.org/10.1007/s00453-004-1090-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-008-9130-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035666083", 
              "https://doi.org/10.1007/s00224-008-9130-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-35452-6_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032367522", 
              "https://doi.org/10.1007/978-3-642-35452-6_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/b:mach.0000033116.57574.95", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005313049", 
              "https://doi.org/10.1023/b:mach.0000033116.57574.95"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-008-9150-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032458581", 
              "https://doi.org/10.1007/s00224-008-9150-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-004-1178-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029329846", 
              "https://doi.org/10.1007/s00224-004-1178-y"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-07-19", 
        "datePublishedReg": "2016-07-19", 
        "description": "For a given graph and an integer t, the Min\u2013Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for t
     

    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-0059-z'

    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-0059-z'

    Turtle is a human-readable linked data format.

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

    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-0059-z'


     

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

    134 TRIPLES      22 PREDICATES      61 URIs      42 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-016-0059-z schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 anzsrc-for:0103
    5 schema:author Ndf693b9634884adab6c8eee78673b155
    6 schema:citation sg:pub.10.1007/978-3-642-11269-0_8
    7 sg:pub.10.1007/978-3-642-35452-6_16
    8 sg:pub.10.1007/978-3-662-44465-8_40
    9 sg:pub.10.1007/s00224-004-1178-y
    10 sg:pub.10.1007/s00224-008-9130-1
    11 sg:pub.10.1007/s00224-008-9150-x
    12 sg:pub.10.1007/s00453-004-1090-5
    13 sg:pub.10.1007/s00453-014-9874-8
    14 sg:pub.10.1023/b:mach.0000033116.57574.95
    15 schema:datePublished 2016-07-19
    16 schema:datePublishedReg 2016-07-19
    17 schema:description For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for t<n/4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t<n/4$$\end{document}, where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let k=t-n/4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=t-n/4$$\end{document}. We show that the problem is polynomial-time solvable when roughly k<n/32\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k<\sqrt{n/32}$$\end{document}. When k∈o(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\in o(n)$$\end{document}, we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in O(2n/r·n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({2}^{n/r}\cdot n^2)$$\end{document} time for k<n/12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k<n/12$$\end{document} and in O(n2·23n/4+k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^2\cdot 2^{3n/4+k})$$\end{document} time for n/12≤k<n/4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n/12\le k< n/4$$\end{document}, where r=2+⌊(n/4-3k-2)/(2k+1)⌋≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2$$\end{document}.
    18 schema:genre article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf Nfcb0a8e68ef54a55b3fa8c028c51268b
    22 Nfcb9ae0a283c483a99242e2d3d993263
    23 sg:journal.1036683
    24 schema:keywords Min–Max 2-Clustering problem
    25 SUBEPT
    26 algorithm
    27 complexity
    28 deterministic algorithm
    29 different ranges
    30 disjoint
    31 edge
    32 edges incident
    33 editing
    34 graph
    35 incidents
    36 integer t
    37 maximal disjoint
    38 min–max 2-cluster editing
    39 modification
    40 number
    41 number of vertices
    42 paper
    43 polynomial time
    44 problem
    45 range
    46 sub-exponential time
    47 time
    48 vertices
    49 schema:name Parameterized algorithms for min–max 2-cluster editing
    50 schema:pagination 47-63
    51 schema:productId N0d804fa97bf242838500a99641102a65
    52 Nf4b1effcda4c412b9a75dd791d79bfa3
    53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032540292
    54 https://doi.org/10.1007/s10878-016-0059-z
    55 schema:sdDatePublished 2021-11-01T18:28
    56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    57 schema:sdPublisher N0b1e875ec6214b56b9a494ef798c7096
    58 schema:url https://doi.org/10.1007/s10878-016-0059-z
    59 sgo:license sg:explorer/license/
    60 sgo:sdDataset articles
    61 rdf:type schema:ScholarlyArticle
    62 N0b1e875ec6214b56b9a494ef798c7096 schema:name Springer Nature - SN SciGraph project
    63 rdf:type schema:Organization
    64 N0d804fa97bf242838500a99641102a65 schema:name dimensions_id
    65 schema:value pub.1032540292
    66 rdf:type schema:PropertyValue
    67 Na9218469cdcc4d06b2a8ff8f09bcea77 rdf:first sg:person.013045767237.23
    68 rdf:rest rdf:nil
    69 Ndf693b9634884adab6c8eee78673b155 rdf:first sg:person.014055212561.22
    70 rdf:rest Na9218469cdcc4d06b2a8ff8f09bcea77
    71 Nf4b1effcda4c412b9a75dd791d79bfa3 schema:name doi
    72 schema:value 10.1007/s10878-016-0059-z
    73 rdf:type schema:PropertyValue
    74 Nfcb0a8e68ef54a55b3fa8c028c51268b schema:volumeNumber 34
    75 rdf:type schema:PublicationVolume
    76 Nfcb9ae0a283c483a99242e2d3d993263 schema:issueNumber 1
    77 rdf:type schema:PublicationIssue
    78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Mathematical Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Pure Mathematics
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Applied Mathematics
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Numerical and Computational Mathematics
    89 rdf:type schema:DefinedTerm
    90 sg:journal.1036683 schema:issn 1382-6905
    91 1573-2886
    92 schema:name Journal of Combinatorial Optimization
    93 schema:publisher Springer Nature
    94 rdf:type schema:Periodical
    95 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
    96 schema:familyName Wu
    97 schema:givenName Bang Ye
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
    99 rdf:type schema:Person
    100 sg:person.014055212561.22 schema:affiliation grid-institutes:grid.412047.4
    101 schema:familyName Chen
    102 schema:givenName Li-Hsuan
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22
    104 rdf:type schema:Person
    105 sg:pub.10.1007/978-3-642-11269-0_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022401414
    106 https://doi.org/10.1007/978-3-642-11269-0_8
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/978-3-642-35452-6_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032367522
    109 https://doi.org/10.1007/978-3-642-35452-6_16
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/978-3-662-44465-8_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044291945
    112 https://doi.org/10.1007/978-3-662-44465-8_40
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/s00224-004-1178-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1029329846
    115 https://doi.org/10.1007/s00224-004-1178-y
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/s00224-008-9130-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035666083
    118 https://doi.org/10.1007/s00224-008-9130-1
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/s00224-008-9150-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1032458581
    121 https://doi.org/10.1007/s00224-008-9150-x
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/s00453-004-1090-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051624082
    124 https://doi.org/10.1007/s00453-004-1090-5
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/s00453-014-9874-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051438401
    127 https://doi.org/10.1007/s00453-014-9874-8
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1023/b:mach.0000033116.57574.95 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005313049
    130 https://doi.org/10.1023/b:mach.0000033116.57574.95
    131 rdf:type schema:CreativeWork
    132 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
    133 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
    134 rdf:type schema:Organization
     




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


    ...