In this paper, we propose a new heuristic algorithm for the maximum consensus tree of rooted triples. By means of the experimental results, we show that the algorithm is better than the three previous heuristics and runs in a reasonable amount of time. Furthermore, using the algorithm, it is possible to achieve a trade-off between the running time and the quality of the solution. We also investigate the computational complexity of the maximum compatible set problem. We show that it is NP-hard to find the maximum vertex set compatible with given rooted triples.