Finding smallest supertrees under minor containment

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The diversity of application areas relying on tree-structured data results in a wide interest in algorithms which determine differences or similarities among trees. One way of measuring the similarity between trees is to find the smallest common superstructure or supertree, where common elements are typically defined in terms of a mapping or embedding. In the simplest case, a supertree will contain exact copies of each input tree, so that for each input tree, each vertex of a tree can be mapped to a vertex in the supertree such that each edge maps to the corresponding edge. More general mappings allow for the extraction of more subtle common elements captured by looser definitions of similarity. We consider supertrees under the general mapping of minor containment. Minor containment generalizes both subgraph isomorphism and topological embedding; as a consequence of this generality, however, it is NP-complete to determine whether or not G is a minor of H, even for general trees. By focusing on trees of bounded degree, we obtain an O(n3) algorithm which determines the smallest tree T such that both of the input trees are minors of T, even when the trees are assumed to be unrooted and unordered.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 25th International Workshop, WG 1999, Proceedings
EditorsPeter Widmayer, Gabriele Neyer, Stephan Eidenbenz
PublisherSpringer Verlag
Pages303-312
Number of pages10
ISBN (Print)3540667318, 9783540667315
DOIs
StatePublished - 1999
Event25th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1999 - Ascona, Switzerland
Duration: Jun 17 1999Jun 19 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1665
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1999
Country/TerritorySwitzerland
CityAscona
Period6/17/996/19/99

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Finding smallest supertrees under minor containment'. Together they form a unique fingerprint.

Cite this