Outputs (4)

Frameworks for logically classifying polynomial-time optimisation problems (2010)
Presentation / Conference Contribution
Gate, J., & Stewart., I. (2010, June). Frameworks for logically classifying polynomial-time optimisation problems. Presented at 5th International Computer Science Symposium in Russia (CSR 2010), Kazan, Russia

We show that a logical framework, based around a fragment of existential second-order logic formerly proposed by others so as to capture the class of polynomially-bounded P-optimisation problems, cannot hope to do so, under the assumption that P ≠ NP... Read More about Frameworks for logically classifying polynomial-time optimisation problems.

A class of hierarchical graphs as topologies for interconnection networks (2010)
Journal Article
Lai, P., Hsu, H., Tsai, C., & Stewart, I. (2010). A class of hierarchical graphs as topologies for interconnection networks. Theoretical Computer Science, 411(31-33), 2912-2924. https://doi.org/10.1016/j.tcs.2010.04.022

We study some topological and algorithmic properties of a recently defined hierarchical interconnection network, the hierarchical crossed cube HCC(k,n), which draws upon constructions used within the well-known hypercube and also the crossed cube. In... Read More about A class of hierarchical graphs as topologies for interconnection networks.

A general algorithm for detecting faults under the comparison diagnosis model (2010)
Presentation / Conference Contribution
Stewart, I. (2010, April). A general algorithm for detecting faults under the comparison diagnosis model. Presented at 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Atlanta, Georgia, U.S.A

We develop a widely applicable algorithm to solve the fault diagnosis problem in certain distributed-memory multiprocessor systems in which there are a limited number of faulty processors. In particular, we prove that if the underlying graph G = (V,E... Read More about A general algorithm for detecting faults under the comparison diagnosis model.

One-to-many node-disjoint paths in (n,k)-star graphs (2010)
Journal Article
Stewart, I., & Xiang, Y. (2010). One-to-many node-disjoint paths in (n,k)-star graphs. Discrete Applied Mathematics, 158(1), 62-70. https://doi.org/10.1016/j.dam.2009.08.013

We present an algorithm which given a source node and a set of n−1 target nodes in the (n,k)-star graph Sn,k, where all nodes are distinct, builds a collection of n−1 node-disjoint paths, one from each target node to the source. The collection of pat... Read More about One-to-many node-disjoint paths in (n,k)-star graphs.