Outputs (4)

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.

On the fixed-parameter tractability of parameterized model-checking problems (2008)
Journal Article
Stewart, I. (2008). On the fixed-parameter tractability of parameterized model-checking problems. Information Processing Letters, 106(1), 33-36. https://doi.org/10.1016/j.ipl.2007.09.009

In this note, we show, through the use of examples, how generic results for proving fixed-parameter tractability which apply to restricted classes of structures can sometimes be more widely applied.