Skip to main content

Research Repository

Advanced Search

Outputs (75)

A 3-approximation algorithm for the subtree distance between phylogenies (2008)
Journal Article
Bordewich, M., McCartin, C., & Semple, C. (2008). A 3-approximation algorithm for the subtree distance between phylogenies. Journal of discrete algorithms, 6(3), 458-471. https://doi.org/10.1016/j.jda.2007.10.002

In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a... Read More about A 3-approximation algorithm for the subtree distance between phylogenies.

Presenting software engineering results using structured abstracts: A randomised experiment. (2008)
Journal Article
Budgen, D., Kitchenham, B. A., Charters, S., Turner, M., Brereton, P., & Linkman, S. (2008). Presenting software engineering results using structured abstracts: A randomised experiment. Empirical Software Engineering, 13(4), 435-468. https://doi.org/10.1007/s10664-008-9075-7

When conducting a systematic literature review, researchers usually determine the relevance of primary studies on the basis of title and abstract. However, experience indicates that the abstracts for many software engineering papers are of too poor a... Read More about Presenting software engineering results using structured abstracts: A randomised experiment..

Embedding long paths in k-ary n-cubes with faulty nodes and links (2008)
Journal Article
Stewart, I., & Xiang, Y. (2008). Embedding long paths in k-ary n-cubes with faulty nodes and links. IEEE Transactions on Parallel and Distributed Systems, 19(8), 1071-1085. https://doi.org/10.1109/tpds.2007.70787

Let $k \geq 4$ be even and let $n \geq 2$. Consider a faulty k-ary n-cube $Q_n^k$ in which the number of node faults $f_n$ and the number of link faults $f_e$ are such that $f_n + f_e \leq 2n-2$. We prove that given any two healthy nodes s and e of $... Read More about Embedding long paths in k-ary n-cubes with faulty nodes and links.

Computational complexity of auditing finite attributes in statistical databases (2008)
Journal Article
Jonsson, P., & Krokhin, A. (2008). Computational complexity of auditing finite attributes in statistical databases. Journal of Computer and System Sciences, 74(5), 898-909. https://doi.org/10.1016/j.jcss.2008.02.002

We study the computational complexity of auditing finite attributes in databases allowing statistical queries. Given a database that supports statistical queries, the auditing problem is to check whether an attribute can be completely determined or n... Read More about Computational complexity of auditing finite attributes in statistical databases.

The computational complexity of graph contractions II: two tough polynomially solvable cases (2008)
Journal Article
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks, 52(1), 32-56. https://doi.org/10.1002/net.20249

For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This article is part II of our study on the computational complexity of the H-CONTRACTIBILITY problem. In the first ar... Read More about The computational complexity of graph contractions II: two tough polynomially solvable cases.

Constant-Rank Codes (2008)
Presentation / Conference Contribution
Gadouleau, M., & Yan, Z. (2008, July). Constant-Rank Codes. Presented at IEEE ISIT, Toronto, ON

Multi-Colour Sketch Recognition in a Learning Environment (2008)
Presentation / Conference Contribution
Don, L., & Ivrissimtzis, I. (2008, July). Multi-Colour Sketch Recognition in a Learning Environment. Presented at International Workshop on Interactive Digital Entertainment Technologies., Lanzhou, China

Virtual physics environments are becoming increasingly popular as a teaching tool for grade and high school level mechanical physics. While useful, these tools often offer a complex user interface, lacking the intuitive nature of the traditional whit... Read More about Multi-Colour Sketch Recognition in a Learning Environment.