### 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 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees'. Together they form a unique fingerprint.

## 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