@inproceedings{7c1034cf0b7348529f8adadfd818f97c,

title = "A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees",

abstract = "A node-labeled rooted tree T (with root r) is an all-or-nothing subtree (called AoN-subtree) of a node-labeled rooted tree T′ if (1) T is a subtree of the tree rooted at some node u (with the same label as r) of T′, (2) for each internal node v of T, all the neighbors of v in T′ are the neighbors of v in T. Tree T′ is then called an AoN-supertree of T. Given a set of n node-labeled rooted trees, smallest common AoN-supertree problem seeks the smallest possible node-labeled rooted tree (denoted as ) such that every tree Ti in is an AoN-subtree of . It generalizes the smallest superstring problem and it has applications in glycobiology. We present a polynomial-time greedy algorithm with approximation ratio 6.",

author = "Aoki-Kinoshita, {Kiyoko F.} and Minoru Kanehisa and Ming-Yang Kao and Li, {Xiang Yang} and Weizhao Wang",

year = "2006",

doi = "10.1007/11940128_12",

language = "English (US)",

isbn = "3540496947",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "100--110",

booktitle = "Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings",

note = "17th International Symposium on Algorithms and Computation, ISAAC 2006 ; Conference date: 18-12-2006 Through 20-12-2006",

}