Drawing (Complete) Binary Tanglegrams. Buchin, K., Buchin, M., Byrka, J., Nöllenburg, M., Okamoto, Y., Silveira, R., & Wolff, A. Algorithmica, 62(1):309–332, Springer New York, 2012. doi abstract bibtex A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O ( n 3 )-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.
@Article{buchin12drawing,
author = {Buchin, Kevin and Buchin, Maike and Byrka, Jaroslaw and N\"ollenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo and Wolff, Alexander},
title = {Drawing (Complete) Binary Tanglegrams},
journal = {Algorithmica},
year = {2012},
volume = {62},
number = {1--2},
pages = {309--332},
issn = {0178-4617},
abstract = {A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O ( n 3 )-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.},
affiliation = {Faculteit Wiskunde en Informatica, TU Eindhoven, Eindhoven, The Netherlands},
doi = {10.1007/s00453-010-9456-3},
number = {1},
keyword = {Informatik},
keywords = {fpt; tanglegrams},
owner = {Sebastian},
publisher = {Springer New York},
timestamp = {2012.02.07},
}
Downloads: 0
{"_id":"4MWW9u8ZeNsxiHRP5","bibbaseid":"buchin-buchin-byrka-nllenburg-okamoto-silveira-wolff-drawingcompletebinarytanglegrams-2012","author_short":["Buchin, K.","Buchin, M.","Byrka, J.","Nöllenburg, M.","Okamoto, Y.","Silveira, R.","Wolff, A."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Buchin"],"firstnames":["Kevin"],"suffixes":[]},{"propositions":[],"lastnames":["Buchin"],"firstnames":["Maike"],"suffixes":[]},{"propositions":[],"lastnames":["Byrka"],"firstnames":["Jaroslaw"],"suffixes":[]},{"propositions":[],"lastnames":["Nöllenburg"],"firstnames":["Martin"],"suffixes":[]},{"propositions":[],"lastnames":["Okamoto"],"firstnames":["Yoshio"],"suffixes":[]},{"propositions":[],"lastnames":["Silveira"],"firstnames":["Rodrigo"],"suffixes":[]},{"propositions":[],"lastnames":["Wolff"],"firstnames":["Alexander"],"suffixes":[]}],"title":"Drawing (Complete) Binary Tanglegrams","journal":"Algorithmica","year":"2012","volume":"62","number":"1","pages":"309–332","issn":"0178-4617","abstract":"A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O ( n 3 )-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.","affiliation":"Faculteit Wiskunde en Informatica, TU Eindhoven, Eindhoven, The Netherlands","doi":"10.1007/s00453-010-9456-3","keyword":["fpt; tanglegrams"],"keywords":"fpt; tanglegrams","owner":"Sebastian","publisher":"Springer New York","timestamp":"2012.02.07","bibtex":"@Article{buchin12drawing,\n author = {Buchin, Kevin and Buchin, Maike and Byrka, Jaroslaw and N\\\"ollenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo and Wolff, Alexander},\n title = {Drawing (Complete) Binary Tanglegrams},\n journal = {Algorithmica},\n year = {2012},\n volume = {62},\n number = {1--2},\n pages = {309--332},\n issn = {0178-4617},\n abstract = {A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O ( n 3 )-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.},\n affiliation = {Faculteit Wiskunde en Informatica, TU Eindhoven, Eindhoven, The Netherlands},\n doi = {10.1007/s00453-010-9456-3},\n number = {1},\n keyword = {Informatik},\n keywords = {fpt; tanglegrams},\n owner = {Sebastian},\n publisher = {Springer New York},\n timestamp = {2012.02.07},\n}\n\n","author_short":["Buchin, K.","Buchin, M.","Byrka, J.","Nöllenburg, M.","Okamoto, Y.","Silveira, R.","Wolff, A."],"key":"buchin12drawing","id":"buchin12drawing","bibbaseid":"buchin-buchin-byrka-nllenburg-okamoto-silveira-wolff-drawingcompletebinarytanglegrams-2012","role":"author","urls":{},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","dataSources":["C5FtkvWWggFfMJTFX"],"keywords":["fpt; tanglegrams"],"search_terms":["drawing","complete","binary","tanglegrams","buchin","buchin","byrka","nöllenburg","okamoto","silveira","wolff"],"title":"Drawing (Complete) Binary Tanglegrams","year":2012}