Skip to main content

Research Repository

Advanced Search

All Outputs (44)

Mixing 3-colourings in bipartite graphs (2007)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (online). Mixing 3-colourings in bipartite graphs. Lecture Notes in Computer Science, 166-177. https://doi.org/10.1007/978-3-540-74839-7_17

For a 3-colourable graph G, the 3-colour graph of G, denoted C3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the foll... Read More about Mixing 3-colourings in bipartite graphs.

Covering Graphs with Few Complete Bipartite Subgraphs (2007)
Presentation / Conference Contribution
Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2007, December). Covering Graphs with Few Complete Bipartite Subgraphs. Presented at FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, New Delhi, India

User interface challenges for the World Wide Web (2007)
Book Chapter
Ashman, H., Brailsford, T., Burnett, G., Goulding, J., Moore, A., Stewart, C., & Truran, M. (2007). User interface challenges for the World Wide Web. In Human-Computer Interaction Handbook (559-572). CRC Press

Upper Bounds and Algorithms for Parallel Knock-Out Numbers (2007)
Presentation / Conference Contribution
Broersma, H., Johnson, M., & Paulusma, D. (2007, June). Upper Bounds and Algorithms for Parallel Knock-Out Numbers. Presented at SIROCCO 2007: Structural Information and Communication Complexity, Castiglioncello, Italy

Considering Video as a Volume (2007)
Presentation / Conference Contribution
Flitton, G., & Breckon, T. (2007, November). Considering Video as a Volume. Presented at Proc. 4th European Conference on Visual Media Production

Covering Properties of Rank Metric Codes (2007)
Presentation / Conference Contribution
Gadouleau, M., & Yan, Z. (2007, November). Covering Properties of Rank Metric Codes. Presented at IEEE Globecom, Washington, DC

Distributed selfish load balancing (2007)
Journal Article
Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P. W., Hu, Z., Hu, Z. H., Martin, R. A., & Martin, R. (2007). Distributed selfish load balancing. SIAM Journal on Computing, 37(4), 1163-1181. https://doi.org/10.1137/060660345

Suppose that a set of m tasks are to be shared as equally as possible amongst a set of n resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a "selfish agent", and require each agent to select a resource... Read More about Distributed selfish load balancing.

Software Architecture Visualization: An Evaluation Framework and Its Application (2007)
Journal Article
Gallagher, K., Hatch, A., & Munro, M. (2008). Software Architecture Visualization: An Evaluation Framework and Its Application. IEEE Transactions on Software Engineering, 34(2), 260-270. https://doi.org/10.1109/tse.2007.70757

In order to characterize and improve software architecture visualization practice, the paper derives and constructs a qualitative framework, with 7 key areas and 31 features, for the assessment of software architecture visualization tools. The framew... Read More about Software Architecture Visualization: An Evaluation Framework and Its Application.

Reducing Regression Test Size by Exclusion (2007)
Presentation / Conference Contribution
Gallagher, K., Hall, T., Black, S., Tahvildari, L., & Canfora, G. (2007, October). Reducing Regression Test Size by Exclusion. Presented at 23rd International Conference on Software Maintenance, Paris, France

Operational software is constantly evolving. Regression testing is used to identify the unintended consequences of evolutionary changes. As most changes affect only a small proportion of the system, the challenge is to ensure that the regression test... Read More about Reducing Regression Test Size by Exclusion.

Parameterized proof complexity (2007)
Presentation / Conference Contribution
Dantchev, S., Martin, B., & Szeider, S. (2007, October). Parameterized proof complexity. Presented at 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, USA

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional CNF formula cannot be satisfied by a truth assignment that se... Read More about Parameterized proof complexity.

Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links (2007)
Journal Article
Stewart, I. (2007). Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links. Journal of Interconnection Networks, 8(3), 253-284. https://doi.org/10.1142/s0219265907002016

We derive a sequential algorithm Find-Ham-Cycle with the following property. On input: k and n (specifying the k-ary n-cube Q(n,k); F, a set of at most 2n-2 faulty links; and v, a node of Q(n,k), the algorithm outputs nodes v+ and v- such that if Fin... Read More about Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links.