### 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 T_{i} 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.

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings |

Pages | 100-110 |

Number of pages | 11 |

DOIs | |

State | Published - Dec 1 2006 |

Event | 17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, India Duration: Dec 18 2006 → Dec 20 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4288 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 17th International Symposium on Algorithms and Computation, ISAAC 2006 |
---|---|

Country | India |

City | Kolkata |

Period | 12/18/06 → 12/20/06 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings*(pp. 100-110). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS). https://doi.org/10.1007/11940128_12

}

*Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4288 LNCS, pp. 100-110, 17th International Symposium on Algorithms and Computation, ISAAC 2006, Kolkata, India, 12/18/06. https://doi.org/10.1007/11940128_12

**A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees.** / Aoki-Kinoshita, Kiyoko F.; Kanehisa, Minoru; Kao, Ming-Yang; Li, Xiang Yang; Wang, Weizhao.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees

AU - Aoki-Kinoshita, Kiyoko F.

AU - Kanehisa, Minoru

AU - Kao, Ming-Yang

AU - Li, Xiang Yang

AU - Wang, Weizhao

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77249162232&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77249162232&partnerID=8YFLogxK

U2 - 10.1007/11940128_12

DO - 10.1007/11940128_12

M3 - Conference contribution

AN - SCOPUS:77249162232

SN - 3540496947

SN - 9783540496946

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 100

EP - 110

BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings

ER -