On the parameterized complexity of the Multi-MCT and Multi-MCST problems |
| |
| Authors: | Wenbin Chen Matthew C. Schmidt Nagiza F. Samatova |
| |
| Affiliation: | 1.Computer Science Department,North Carolina State University,Raleigh,USA;2.Computer Science and Mathematics Division,Oak Ridge National Laboratory,Oak Ridge,USA |
| |
| Abstract: | The comparison of tree structured data is widespread since trees can be used to represent wide varieties of data, such as
XML data, evolutionary histories, or carbohydrate structures. Two graph-theoretical problems used in the comparison of such
data are the problems of finding the maximum common subtree (MCT) and the minimum common supertree (MCST) of two trees. These
problems generalize to the problem of finding the MCT and MCST of multiple trees (Multi-MCT and Multi-MCST, respectively). In this paper, we prove parameterized complexity hardness results for the different parameterized versions
of the Multi-MCT and Multi-MCST problem under isomorphic embeddings. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
