An improved parameterized algorithm for the p-cluster vertex deletion problem

Ontology type: schema:ScholarlyArticle

Article Info

DATE

2015-10-23

AUTHORS ABSTRACT

In the p-Cluster Vertex Deletion problem, we are given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let r=p/k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r=p/k$$\end{document}. In this paper, we design a branching algorithm with time complexity O(αk+|V||E|)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\alpha ^k+|V||E|)$$\end{document}, where α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha$$\end{document} depends on r and has a rough upper bound min{1.6181+r,2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{1.618^{1+r},2\}$$\end{document}. With a more precise analysis, we show that α=1.28·3.57r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha =1.28\cdot 3.57^{r}$$\end{document} for r≤0.219\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\le 0.219$$\end{document}; α=(1-r)r-1r-r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha =(1-r)^{r-1}r^{-r}$$\end{document} for 0.219 More... »

PAGES

373-388

Journal

TITLE

Journal of Combinatorial Optimization

ISSUE

2

VOLUME

33

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10878-015-9969-4

DOI

http://dx.doi.org/10.1007/s10878-015-9969-4

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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": "Wu",
"givenName": "Bang Ye",
"id": "sg:person.013045767237.23",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
],
"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": "Chen",
"givenName": "Li-Hsuan",
"id": "sg:person.014055212561.22",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22"
],
"type": "Person"
}
],
"citation": [
{
"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-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"
},
{
"id": "sg:pub.10.1007/s00224-015-9631-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026521108",
"https://doi.org/10.1007/s00224-015-9631-7"
],
"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/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/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"
}
],
"datePublished": "2015-10-23",
"datePublishedReg": "2015-10-23",
"description": "In the p-Cluster Vertex Deletion problem, we are given a graph G=(V,E)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G=(V,E)$$\\end{document} and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let r=p/k\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$r=p/k$$\\end{document}. In this paper, we design a branching algorithm with time complexity O(\u03b1k+|V||E|)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(\\alpha ^k+|V||E|)$$\\end{document}, where \u03b1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\alpha$$\\end{document} depends on r and has a rough upper bound min{1.6181+r,2}\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\min \\{1.618^{1+r},2\\}$$\\end{document}. With a more precise analysis, we show that \u03b1=1.28\u00b73.57r\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\alpha =1.28\\cdot 3.57^{r}$$\\end{document} for r\u22640.219\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$r\\le 0.219$$\\end{document}; \u03b1=(1-r)r-1r-r\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\alpha =(1-r)^{r-1}r^{-r}$$\\end{document} for 0.219
 
 
   
 Download the RDF metadata as:  HOW TO GET THIS DATA PROGRAMMATICALLY: JSON-LD N-Triples Turtle RDF/XML 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-015-9969-4' 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-015-9969-4' Turtle is a human-readable linked data format. curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-015-9969-4' RDF/XML is a standard XML format for linked data. curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-015-9969-4'   This table displays all metadata directly associated to this object as RDF triples. 135 TRIPLES      22 PREDICATES      65 URIs      47 LITERALS      6 BLANK NODES Subject Predicate Object 1 sg:pub.10.1007/s10878-015-9969-4 schema:about anzsrc-for:01 2 ″ ″ anzsrc-for:0101 3 ″ ″ anzsrc-for:0102 4 ″ ″ anzsrc-for:0103 5 ″ schema:author N1756d7413fc64cb18da70565cb5fe8fa 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/s00224-004-1178-y 9 ″ ″ sg:pub.10.1007/s00224-008-9130-1 10 ″ ″ sg:pub.10.1007/s00224-008-9150-x 11 ″ ″ sg:pub.10.1007/s00224-015-9631-7 12 ″ ″ sg:pub.10.1007/s00453-004-1090-5 13 ″ ″ sg:pub.10.1007/s00453-014-9874-8 14 ″ schema:datePublished 2015-10-23 15 ″ schema:datePublishedReg 2015-10-23 16 ″ schema:description In the p-Cluster Vertex Deletion problem, we are given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let r=p/k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r=p/k$$\end{document}. In this paper, we design a branching algorithm with time complexity O(αk+|V||E|)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\alpha ^k+|V||E|)$$\end{document}, where α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha$$\end{document} depends on r and has a rough upper bound min{1.6181+r,2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{1.618^{1+r},2\}$$\end{document}. With a more precise analysis, we show that α=1.28·3.57r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha =1.28\cdot 3.57^{r}$$\end{document} for r≤0.219\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\le 0.219$$\end{document}; α=(1-r)r-1r-r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha =(1-r)^{r-1}r^{-r}$$\end{document} for 0.219<r<1/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0.219< r<1/2$$\end{document}; and α=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha =2$$\end{document} for r≥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\ge 1/2$$\end{document}, respectively. Our algorithm also works with the same time complexity for the variant that the number of clusters is at most p. Our result improves the previous best time complexity O∗(1.84p+k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^*(1.84^{p+k})$$\end{document} and implies that for fixed p the problem can be solved as efficiently as Vertex Cover. 17 ″ schema:genre article 18 ″ schema:inLanguage en 19 ″ schema:isAccessibleForFree false 20 ″ schema:isPartOf Nab99ecbef6f9414aac91646a0a68bacf 21 ″ ″ Nbbdfad1449974e43bdb10132c9084ca6 22 ″ ″ sg:journal.1036683 23 ″ schema:keywords Cluster Vertex Deletion problem 24 ″ ″ Deletion problem 25 ″ ″ algorithm 26 ″ ″ analysis 27 ″ ″ better time complexity 28 ″ ″ branching algorithm 29 ″ ″ cliques 30 ″ ″ clusters 31 ″ ″ complexity 32 ″ ″ cover 33 ″ ″ disjoint maximal cliques 34 ″ ″ goal 35 ″ ″ graph 36 ″ ″ maximal cliques 37 ″ ″ number 38 ″ ″ number of clusters 39 ″ ″ paper 40 ″ ″ parameter k 41 ″ ″ precise analysis 42 ″ ″ previous best time complexity 43 ″ ″ problem 44 ″ ″ removal 45 ″ ″ results 46 ″ ″ same time complexity 47 ″ ″ subset X 48 ″ ″ time complexity 49 ″ ″ variants 50 ″ ″ vertex cover 51 ″ ″ vertex deletion problem 52 ″ ″ vertices 53 ″ schema:name An improved parameterized algorithm for the p-cluster vertex deletion problem 54 ″ schema:pagination 373-388 55 ″ schema:productId N3c7e5f831cef420caffd4a3abb9e35cb 56 ″ ″ N51c564c437304abe9855d145a3eebab9 57 ″ schema:sameAs https://app.dimensions.ai/details/publication/pub.1027437306 58 ″ ″ https://doi.org/10.1007/s10878-015-9969-4 59 ″ schema:sdDatePublished 2021-12-01T19:34 60 ″ schema:sdLicense https://scigraph.springernature.com/explorer/license/ 61 ″ schema:sdPublisher N4ad7d15bae6848ec9eb061b8093903bb 62 ″ schema:url https://doi.org/10.1007/s10878-015-9969-4 63 ″ sgo:license sg:explorer/license/ 64 ″ sgo:sdDataset articles 65 ″ rdf:type schema:ScholarlyArticle 66 N1756d7413fc64cb18da70565cb5fe8fa rdf:first sg:person.013045767237.23 67 ″ rdf:rest Na9d7c0f4a8c94ec89a56428dd25dcaa9 68 N3c7e5f831cef420caffd4a3abb9e35cb schema:name doi 69 ″ schema:value 10.1007/s10878-015-9969-4 70 ″ rdf:type schema:PropertyValue 71 N4ad7d15bae6848ec9eb061b8093903bb schema:name Springer Nature - SN SciGraph project 72 ″ rdf:type schema:Organization 73 N51c564c437304abe9855d145a3eebab9 schema:name dimensions_id 74 ″ schema:value pub.1027437306 75 ″ rdf:type schema:PropertyValue 76 Na9d7c0f4a8c94ec89a56428dd25dcaa9 rdf:first sg:person.014055212561.22 77 ″ rdf:rest rdf:nil 78 Nab99ecbef6f9414aac91646a0a68bacf schema:volumeNumber 33 79 ″ rdf:type schema:PublicationVolume 80 Nbbdfad1449974e43bdb10132c9084ca6 schema:issueNumber 2 81 ″ rdf:type schema:PublicationIssue 82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for: 83 ″ schema:name Mathematical Sciences 84 ″ rdf:type schema:DefinedTerm 85 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for: 86 ″ schema:name Pure Mathematics 87 ″ rdf:type schema:DefinedTerm 88 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for: 89 ″ schema:name Applied Mathematics 90 ″ rdf:type schema:DefinedTerm 91 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for: 92 ″ schema:name Numerical and Computational Mathematics 93 ″ rdf:type schema:DefinedTerm 94 sg:journal.1036683 schema:issn 1382-6905 95 ″ ″ 1573-2886 96 ″ schema:name Journal of Combinatorial Optimization 97 ″ schema:publisher Springer Nature 98 ″ rdf:type schema:Periodical 99 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4 100 ″ schema:familyName Wu 101 ″ schema:givenName Bang Ye 102 ″ schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23 103 ″ rdf:type schema:Person 104 sg:person.014055212561.22 schema:affiliation grid-institutes:grid.412047.4 105 ″ schema:familyName Chen 106 ″ schema:givenName Li-Hsuan 107 ″ schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22 108 ″ rdf:type schema:Person 109 sg:pub.10.1007/978-3-642-11269-0_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022401414 110 ″ ″ https://doi.org/10.1007/978-3-642-11269-0_8 111 ″ rdf:type schema:CreativeWork 112 sg:pub.10.1007/978-3-642-35452-6_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032367522 113 ″ ″ https://doi.org/10.1007/978-3-642-35452-6_16 114 ″ rdf:type schema:CreativeWork 115 sg:pub.10.1007/s00224-004-1178-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1029329846 116 ″ ″ https://doi.org/10.1007/s00224-004-1178-y 117 ″ rdf:type schema:CreativeWork 118 sg:pub.10.1007/s00224-008-9130-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035666083 119 ″ ″ https://doi.org/10.1007/s00224-008-9130-1 120 ″ rdf:type schema:CreativeWork 121 sg:pub.10.1007/s00224-008-9150-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1032458581 122 ″ ″ https://doi.org/10.1007/s00224-008-9150-x 123 ″ rdf:type schema:CreativeWork 124 sg:pub.10.1007/s00224-015-9631-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026521108 125 ″ ″ https://doi.org/10.1007/s00224-015-9631-7 126 ″ rdf:type schema:CreativeWork 127 sg:pub.10.1007/s00453-004-1090-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051624082 128 ″ ″ https://doi.org/10.1007/s00453-004-1090-5 129 ″ rdf:type schema:CreativeWork 130 sg:pub.10.1007/s00453-014-9874-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051438401 131 ″ ″ https://doi.org/10.1007/s00453-014-9874-8 132 ″ rdf:type schema:CreativeWork 133 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, Chiayi, Taiwan, ROC 134 ″ schema:name National Chung Cheng University, 621, Chiayi, Taiwan, ROC 135 ″ rdf:type schema:Organization   
 
 
 Preview window. Press ESC to close (or click here) ... 
 SN SciGraph Explorer      |     © Springer Nature 2017-2021      |     Quicklinks:   Getting Started  |  Downloads // make tabs persistent // https://stackoverflow.com/questions/9685968/best-way-to-make-twitter-bootstrap-tabs-persistent $(document).ready(function() { // show active tab on reload if (location.hash !== '')$('a[href="' + location.hash + '"]').tab('show'); // remember the hash in the URL without jumping $('a[data-toggle="tab"]').on('shown.bs.tab', function(e) { if(history.pushState) { history.pushState(null, null, '#'+$(e.target).attr('href').substr(1)); } else { location.hash = '#'+$(e.target).attr('href').substr(1); } }); }); // Enable tooltips everywhere$(function () { $('[data-toggle="tooltip"]').tooltip({ 'html' : true , }) }) // TABS CONTROLLER // use to load viz when tab is clicked var viz_first_time = true;$('#topTabs a[data-toggle=tab]').on('shown.bs.tab', function (e){ //e.preventDefault(); var target = $(e.target).attr("href"); console.log('Tab: ' + target); if (target == '#tabvisual') { if (viz_first_time) { console.log('Rendering dataviz..'); render_viz('mynetwork', nodeData, edgeData); viz_first_time = false; } }$(this).tab('show'); }); // SLIDE REVEAL // USE WITH: slider.slideReveal("show"); var slider = $('#slider').slideReveal({ push: true, overlay: false, width: 600, speed: 700 }); // legacy function resize(size) { // expand/collapse div with graph if (size == "compact") { if ($("#overview_graph_div").hasClass("col-md-12")) { $("#overview_graph_div").removeClass("col-md-12").addClass("col-md-6");$("#details_div").removeClass("col-md-12").addClass("col-md-6"); $("#compact_button").addClass("active");$("#wide_button").removeClass("active"); } } else if (size == "wide") { if ($("#overview_graph_div").hasClass("col-md-6")) {$("#overview_graph_div").removeClass("col-md-6").addClass("col-md-12"); $("#details_div").removeClass("col-md-6").addClass("col-md-12");$("#wide_button").addClass("active"); $("#compact_button").removeClass("active"); } } } function render_viz(container) { // create a network var container = document.getElementById(container); // provide the data in the vis format var data = { nodes: nodes, edges: edges }; // initialize your network! var network = new vis.Network(container, data, options); network.on('click', actionPreviewRdf); network.on('doubleClick', actionJumpPage); network.fit(); } var bclick=false; function actionPreviewRdf(data) { data.event.preventDefault(); if (data.nodes) { // console.log(data.nodes); var thisnode_id = data.nodes[0]; // assuming one node is clicked at a time! var node = nodes.get(thisnode_id); if (node.uri && node.group!='text' && node.group!='undefined' && node.uri!='http://scigraph.springernature.com/pub.10.1007/s10878-015-9969-4') { //console.log(node.uri);$("#side_title").html("<a title='Open in new page' href='/resource?u=" + node.uri + "'>" + node.label + "</a>"); fillInURIpreview(node.uri); setTimeout(function () { if (!bclick){ slider.slideReveal("show"); bclick=false; } }, 500); } } } function actionJumpPage(data) { // https://github.com/almende/vis/issues/743 data.event.preventDefault(); if (data.nodes) { bclick=true; // console.log(data.nodes); var thisnode_id = data.nodes[0]; // assuming one node is clicked at a time! var node = nodes.get(thisnode_id); if(node.uri && node.group!='text' && node.group!='undefined' && node.uri!='http://scigraph.springernature.com/pub.10.1007/s10878-015-9969-4'){ // console.log(node); url = "/resource?u=" + node.uri; window.location.href=url; } } } function fillInURIpreview(uri_hash_safe) { $("#slide_contents").empty();$("#slide_contents").html("<i>loading..</i>"); $.get( "/explorer/ajax_resource?u=" + uri_hash_safe, // {u : uri_hash_safe}, // => causes unwanted char encodings! function(data) {$("#slide_contents").html(data); } ); } // create an array with nodes var nodeData=[ { id: "https://app.dimensions.ai/details/publication/pub.1027437306", label: "https://app.dimensions.ai/details/publication/pub.1027437306", uri : "https://app.dimensions.ai/details/publication/pub.1027437306", group: "text" }, { id: "rdf:type", label: "rdf:type", uri : "http://www.w3.org/1999/02/22-rdf-syntax-ns*hash*type", group: "predicate_uri", color:{border:'#4ae54a'}, }, { id: "schema:about", label: "schema:about", uri : "http://schema.org/about", group: "predicate_uri", color:{border:'#9E9E9E'}, }, { id: "anzsrc\u002Dfor:01", label: "Mathematical Sciences", uri : "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", group: "concept" }, { id: "sg:journal.1036683", label: "Journal of Combinatorial Optimization", uri : "http://scigraph.springernature.com/journal.1036683", group: "journal" }, { id: "anzsrc\u002Dfor:0101", label: "Pure Mathematics", uri : "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", group: "concept" }, { id: "anzsrc\u002Dfor:0103", label: "Numerical and Computational Mathematics", uri : "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", group: "concept" }, { id: "anzsrc\u002Dfor:0102", label: "Applied Mathematics", uri : "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", group: "concept" }, { id: "schema:sameAs", label: "schema:sameAs", uri : "http://schema.org/sameAs", group: "predicate_uri", color:{border:'#9E9E9E'}, }, { id: "sg:pub.10.1007/s00453\u002D004\u002D1090\u002D5", label: "sg:pub.10.1007/s00453\u002D004\u002D1090\u002D5", uri : "http://scigraph.springernature.com/pub.10.1007/s00453-004-1090-5", group: "article" }, { id: "sg:pub.10.1007/s00453\u002D014\u002D9874\u002D8", label: "sg:pub.10.1007/s00453\u002D014\u002D9874\u002D8", uri : "http://scigraph.springernature.com/pub.10.1007/s00453-014-9874-8", group: "article" }, { id: "https://doi.org/10.1007/s10878\u002D015\u002D9969\u002D4", label: "https://doi.org/10.1007/s10878\u002D015\u002D9969\u002D4", uri : "https://doi.org/10.1007/s10878-015-9969-4", group: "text" }, { id: "sg:pub.10.1007/s00224\u002D004\u002D1178\u002Dy", label: "sg:pub.10.1007/s00224\u002D004\u002D1178\u002Dy", uri : "http://scigraph.springernature.com/pub.10.1007/s00224-004-1178-y", group: "article" }, { id: "schema:isPartOf", label: "schema:isPartOf", uri : "http://schema.org/isPartOf", group: "predicate_uri", color:{border:'#9E9E9E'}, }, { id: "sg:pub.10.1007/s00224\u002D008\u002D9130\u002D1", label: "sg:pub.10.1007/s00224\u002D008\u002D9130\u002D1", uri : "http://scigraph.springernature.com/pub.10.1007/s00224-008-9130-1", group: "article" }, { id: "sg:pub.10.1007/s00224\u002D015\u002D9631\u002D7", label: "sg:pub.10.1007/s00224\u002D015\u002D9631\u002D7", uri : "http://scigraph.springernature.com/pub.10.1007/s00224-015-9631-7", group: "article" }, { id: "sg:pub.10.1007/978\u002D3\u002D642\u002D35452\u002D6_16", label: "sg:pub.10.1007/978\u002D3\u002D642\u002D35452\u002D6_16", uri : "http://scigraph.springernature.com/pub.10.1007/978-3-642-35452-6_16", group: "article" }, { id: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", label: "An improved parameterized algorithm for the p\u002Dcluster ...", uri : "http://scigraph.springernature.com/pub.10.1007/s10878-015-9969-4", icon: { size: 110, color: 'grey'}, group: "article" }, { id: "sg:pub.10.1007/978\u002D3\u002D642\u002D11269\u002D0_8", label: "sg:pub.10.1007/978\u002D3\u002D642\u002D11269\u002D0_8", uri : "http://scigraph.springernature.com/pub.10.1007/978-3-642-11269-0_8", group: "article" }, { id: "schema:ScholarlyArticle", label: "schema:ScholarlyArticle", uri : "http://schema.org/ScholarlyArticle", group: "text" }, { id: "sg:pub.10.1007/s00224\u002D008\u002D9150\u002Dx", label: "sg:pub.10.1007/s00224\u002D008\u002D9150\u002Dx", uri : "http://scigraph.springernature.com/pub.10.1007/s00224-008-9150-x", group: "article" }, { id: "schema:citation", label: "schema:citation", uri : "http://schema.org/citation", group: "predicate_uri", color:{border:'#9E9E9E'}, }, ] // console.log(nodeData) // create an array with edges var edgeData=[ { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:about" }, { from: "schema:about", to: "anzsrc\u002Dfor:01" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:about" }, { from: "schema:about", to: "anzsrc\u002Dfor:0101" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:about" }, { from: "schema:about", to: "anzsrc\u002Dfor:0102" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:about" }, { from: "schema:about", to: "anzsrc\u002Dfor:0103" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/978\u002D3\u002D642\u002D11269\u002D0_8" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/978\u002D3\u002D642\u002D35452\u002D6_16" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/s00224\u002D004\u002D1178\u002Dy" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/s00224\u002D008\u002D9130\u002D1" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/s00224\u002D008\u002D9150\u002Dx" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/s00224\u002D015\u002D9631\u002D7" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/s00453\u002D004\u002D1090\u002D5" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:citation" }, { from: "schema:citation", to: "sg:pub.10.1007/s00453\u002D014\u002D9874\u002D8" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:isPartOf" }, { from: "schema:isPartOf", to: "sg:journal.1036683" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:sameAs" }, { from: "schema:sameAs", to: "https://app.dimensions.ai/details/publication/pub.1027437306" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "schema:sameAs" }, { from: "schema:sameAs", to: "https://doi.org/10.1007/s10878\u002D015\u002D9969\u002D4" }, { from: "sg:pub.10.1007/s10878\u002D015\u002D9969\u002D4", to: "rdf:type" }, { from: "rdf:type", to: "schema:ScholarlyArticle" }, ] // console.log(edgeData) var nodes = new vis.DataSet(nodeData); var edges = new vis.DataSet(edgeData); var options = { autoResize: true, clickToUse: false, physics:{ barnesHut:{gravitationalConstant:-30000}, stabilization: {iterations:2500} }, interaction:{ hover: true, navigationButtons: true, zoomView: false }, nodes: { shape: 'dot', size: 30, font: { size: 15, color: 'black' }, borderWidth: 2, }, edges: { color: 'gray', smooth: false, length : 150, arrows: { to: {enabled: true, scaleFactor:0.2, type:'arrow'}, middle: {enabled: false, scaleFactor:1, type:'arrow'}, from: {enabled: false, scaleFactor:1, type:'arrow'} }, }, groups: { primary_uri: { color: { border:'#325D94', background: 'lightyellow', highlight: { border:'#325D94', background: '#FFF59D' }, hover: { border:'#325D94', background: '#FFF59D' }, }, size: 60, font: { size: 18, color: 'black' }, }, predicate_uri: { shape: 'box', color: { background: 'white', border: 'lightgreen', // overridden above highlight: { background: 'white', border: 'red' }, hover: { background: 'white', border: '#F44336' }, }, }, ontology: { // not used shape: 'icon', icon: { face: 'FontAwesome', code: '\uf1db', size: 50, color: 'grey' } }, organization: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf1ad', size: 50, color: '#667eb0' } }, person: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf007', size: 80, color: '#57169a' } }, concept: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf0eb', size: 50, color: '#19b3ee' } }, concept_scheme: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf187', size: 80, color: '#2589b0' } }, article: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf1ea', size: 80, color: '#2589b0' } }, journal: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf115', size: 80, color: '#2589b0' } }, book: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf02d', size: 60, color: '#2589b0' } }, grant: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf0c3', size: 40, color: 'darkblue' } }, conference: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf19d', size: 60, color: '#94190c' } }, metrics: { shape: 'icon', icon: { face: 'FontAwesome', code: '\uf080', size: 40, color: '#b09390' } }, text: { shape: 'text', font: { color: '#343434', }, } } } // NORMALLY this is how you render the viz (done via tabs click) //render_viz('mynetwork', nodeData, edgeData); // EXAMPLE for reusing code for another viz: // \$('#modal_network').on('show.bs.modal', function (event) { // render_viz('network_inside_modal'); // })