Improved methods for computing distances between unordered trees using integer programming

DOI10.1007/978-3-319-71147-8_4zbMATH Open1474.90294arXiv1706.03473OpenAlexW2624871005MaRDI QIDQ1708596FDOQ1708596

Eunpyeong Hong, Yasuaki Kobayashi, Akihiro Yamamoto

Publication date: 26 March 2018

Abstract: Kondo et al. (DS 2014) proposed methods for computing distances between unordered rooted trees by transforming an instance of the distance computing problem into an instance of the integer programming problem. They showed that the tree edit distance, segmental distance, and bottom-up segmental distance problem can be respectively transformed into an integer program which has $O(nm)$ variables and $O(n^2{m}^2)$ constraints, where $n$ and $m$ are the number of nodes of input trees. In this work, we propose new integer programming formulations for these three distances and the bottom-up distance by applying dynamic programming approach. We divide the tree edit distance problem into $O(nm)$ subproblems each of which has only $O(n+m)$ constraints. For the other three distances, each subproblem can be reduced to a maximum weighted matching problem in a bipartite graph which can be solved in polynomial time. In order to evaluate our methods, we compare our method to the previous one due to Kondo et al. The experimental results show that the performance of our methods have been improved remarkably compared to that of the previous method.

Full work available at URL: https://arxiv.org/abs/1706.03473

zbMATH Keywords

dynamic programminginteger programmingtree edit distanceunorderd trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Cited In (3)

• On a quadratic programming problem involving distances in trees
• Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
• Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete

This page was built for publication: Improved methods for computing distances between unordered trees using integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708596)