Skip to main content

Research Repository

Advanced Search

Outputs (64)

Logical and complexity-theoretic aspects of models of computation with restricted access to arrays (2009)
Journal Article
Stewart, I. (2009). Logical and complexity-theoretic aspects of models of computation with restricted access to arrays. Journal of Logic and Computation, 19(1), 217-242. https://doi.org/10.1093/logcom/exn025

We study a class of program schemes, NPSB, in which, aside from basic assignments, non-deterministic guessing and while loops, we have access to arrays; but where these arrays are binary write-once in that they are initialized to 'zero' and can only... Read More about Logical and complexity-theoretic aspects of models of computation with restricted access to arrays.

Bipanconnectivity and bipancyclicity in k-ary n-cubes (2009)
Journal Article
Stewart, I., & Xiang, Y. (2009). Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Transactions on Parallel and Distributed Systems, 20(1), 25-33. https://doi.org/10.1109/tpds.2008.45

In this paper we give precise solutions to problems posed by Wang, An, Pan, Wang and Qu and by Hsieh, Lin and Huang. In particular, we show that Q_n^k is bipanconnected and edge-bipancyclic, when k ≥ 3 and n ≥ 2, and we also show that when k is odd,... Read More about Bipanconnectivity and bipancyclicity in k-ary n-cubes.

Program schemes, queues, the recursive spectrum and zero-one laws (2009)
Journal Article
Stewart, I. (2009). Program schemes, queues, the recursive spectrum and zero-one laws. Fundamenta Informaticae, 91(2), 411-435. https://doi.org/10.3233/fi-2009-0050

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ$_+(1)$, is such that the class of problems accepte... Read More about Program schemes, queues, the recursive spectrum and zero-one laws.

Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies (2008)
Journal Article
Madelaine, F., & Stewart, I. (2008). Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies. Discrete Mathematics, 308(18), 4144-4164. https://doi.org/10.1016/j.disc.2007.08.007

We improve upon the best known upper and lower bounds on the sizes of minimal feedback vertex sets in butterflies. Also, we construct new feedback vertex sets in grids so that for a large number of pairs $(n,m)$, the size of our feedback vertex set i... Read More about Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies.

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.

The computational complexity of the parallel knock-out problem (2008)
Journal Article
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.

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.

Constraint satisfaction, logic and forbidden patterns (2007)
Journal Article
Madelaine, F., & Stewart, I. (2007). Constraint satisfaction, logic and forbidden patterns. SIAM Journal on Computing, 37(1), 132-163. https://doi.org/10.1137/050634840

In the early nineties, Feder and Vardi attempted to find a large sub-class of NP which exhibits a dichotomy; that is, where every problem in the sub-class is either solvable in polynomial-time or NP-complete. Their studies resulted in a candidate cla... Read More about Constraint satisfaction, logic and forbidden patterns.

An infinite hierarchy in a class of polynomial-time program schemes (2006)
Journal Article
Gault, R., & Stewart, I. (2006). An infinite hierarchy in a class of polynomial-time program schemes. Theory of Computing Systems, 39(5), 753-783. https://doi.org/10.1007/s00224-005-1230-6

We define a class of program schemes RFDPS constructed around notions of forall-loops, repeat-loops, arrays and if-then-else instructions, and which take finite structures as inputs, and we examine the class of problems, denoted RFDPS also, accepted... Read More about An infinite hierarchy in a class of polynomial-time program schemes.