@Article{boecker12golden,
  author    = {Sebastian B\"ocker},
  title     = {A golden ratio parameterized algorithm for Cluster Editing},
  journal   = {J Discrete Algorithms},
  year      = {2012},
  volume    = {16},
  pages     = {79--89},
  abstract  = {The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel search tree algorithm for the problem, which improves running time from O*(1.76^k) to O*(1.62^k). In detail, we can show that we can always branch with branching vector (2,1) or better, resulting in the golden ratio as the base of the search tree size. Our algorithm uses a well-known transformation to the integer-weighted counterpart of the problem. To achieve our result, we combine three techniques: First, we show that zero-edges in the graph enforce structural features that allow us to branch more efficiently. Second, by repeatedly branching we can isolate vertices, releasing costs. Finally, we use a known characterization of graphs with few conflicts.},
  doi       = {10.1016/j.jda.2012.04.005},
  file      = {Boecker_GoldenRatioParameterizedAlgorithm_JDiscreteAlgorithms_2012_preprint.pdf:2012/Boecker_GoldenRatioParameterizedAlgorithm_JDiscreteAlgorithms_2012_preprint.pdf:PDF},
  keywords  = {jena; linkpdf; PABI; fpt; cluster editing},
  owner     = {Sebastian},
  timestamp = {2011.01.29},
}

{"_id":"X9LEGBH448ukjM2sa","bibbaseid":"bcker-agoldenratioparameterizedalgorithmforclusterediting-2012","authorIDs":[],"author_short":["Böcker, S."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Sebastian"],"propositions":[],"lastnames":["Böcker"],"suffixes":[]}],"title":"A golden ratio parameterized algorithm for Cluster Editing","journal":"J Discrete Algorithms","year":"2012","volume":"16","pages":"79–89","abstract":"The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel search tree algorithm for the problem, which improves running time from O*(1.76^k) to O*(1.62^k). In detail, we can show that we can always branch with branching vector (2,1) or better, resulting in the golden ratio as the base of the search tree size. Our algorithm uses a well-known transformation to the integer-weighted counterpart of the problem. To achieve our result, we combine three techniques: First, we show that zero-edges in the graph enforce structural features that allow us to branch more efficiently. Second, by repeatedly branching we can isolate vertices, releasing costs. Finally, we use a known characterization of graphs with few conflicts.","doi":"10.1016/j.jda.2012.04.005","file":"Boecker_GoldenRatioParameterizedAlgorithm_JDiscreteAlgorithms_2012_preprint.pdf:2012/Boecker_GoldenRatioParameterizedAlgorithm_JDiscreteAlgorithms_2012_preprint.pdf:PDF","keywords":"jena; linkpdf; PABI; fpt; cluster editing","owner":"Sebastian","timestamp":"2011.01.29","bibtex":"@Article{boecker12golden,\n author = {Sebastian B\\\"ocker},\n title = {A golden ratio parameterized algorithm for Cluster Editing},\n journal = {J Discrete Algorithms},\n year = {2012},\n volume = {16},\n pages = {79--89},\n abstract = {The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel search tree algorithm for the problem, which improves running time from O*(1.76^k) to O*(1.62^k). In detail, we can show that we can always branch with branching vector (2,1) or better, resulting in the golden ratio as the base of the search tree size. Our algorithm uses a well-known transformation to the integer-weighted counterpart of the problem. To achieve our result, we combine three techniques: First, we show that zero-edges in the graph enforce structural features that allow us to branch more efficiently. Second, by repeatedly branching we can isolate vertices, releasing costs. Finally, we use a known characterization of graphs with few conflicts.},\n doi = {10.1016/j.jda.2012.04.005},\n file = {Boecker_GoldenRatioParameterizedAlgorithm_JDiscreteAlgorithms_2012_preprint.pdf:2012/Boecker_GoldenRatioParameterizedAlgorithm_JDiscreteAlgorithms_2012_preprint.pdf:PDF},\n keywords = {jena; linkpdf; PABI; fpt; cluster editing},\n owner = {Sebastian},\n timestamp = {2011.01.29},\n}\n\n","author_short":["Böcker, S."],"key":"boecker12golden","id":"boecker12golden","bibbaseid":"bcker-agoldenratioparameterizedalgorithmforclusterediting-2012","role":"author","urls":{},"keyword":["jena; linkpdf; PABI; fpt; cluster editing"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:29:35.060Z","downloads":0,"keywords":["jena; linkpdf; pabi; fpt; cluster editing"],"search_terms":["golden","ratio","parameterized","algorithm","cluster","editing","böcker"],"title":"A golden ratio parameterized algorithm for Cluster Editing","year":2012,"dataSources":["C5FtkvWWggFfMJTFX"]}