Decision Trees are extremely fast in classification. However, they are slow in construction during learning phase. Is there any paper on complexity analysis of Multiway Split, Multi-Class Decision tree?
About complexity and performance issues in relation with solving Multiway Cut/Split problems, I recommend you refer to the following references and therein bibliographies:
Buchbinder et al., " Simplex Transformations and the Multiway Cut Problem ", 2016 - https://pdfs.semanticscholar.org/5f57/2854a615bf305ab78625424293f7874c5982.pdf jointly with https://simons.berkeley.edu/sites/default/files/docs/8323/simons17.pdf
Buchbinder et al., " Simplex Partitioning via Exponential Clocks and the Multiway Cut Problem ", 2013 - http://schwartz.cswp.cs.technion.ac.il/wp-content/uploads/sites/68/2016/12/MC-BNS13.pdf
Karger et al., " Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut ", 2004 - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.8780&rep=rep1&type=pdf
You may also investigate alternative sources of information in connection with Conformation Dynamics. Follow:
M. Weber, " Meshless Methods in Conformation Dynamics ", PhD dissertation, 2006 - https://www.zib.de/weber/Promotion.pdf
Noé et al., " Projected and Hidden Markov Models for calculating kinetics and metastable states of complex molecules ", 2013 - https://arxiv.org/pdf/1309.3220.pdf
The article suggested by you is quite relevant to my work. Actually I am producing a random forest for reasonably large size data. The algorithm is doing well but not giving the shortest trees as compared to decision tree. But my algorithm is performing fast with incremental learning, hence I wanted to compare the performance w.r.t Decsion tree.