Skip to main content

Research Repository

Advanced Search

Outputs (3167)

Hamiltonian cycles through prescribed edges in k-ary n-cubes. (2011)
Presentation / Conference Contribution
Stewart, I. (2011, December). Hamiltonian cycles through prescribed edges in k-ary n-cubes. Presented at 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA'11., Zhangjiajie, China

We prove that if P is a set of at most 2n − 1 edges in a k-ary n-cube, where k ≥ 4 and n ≥ 2, then there is a Hamiltonian cycle on which every edge of P lies if, and only if, the subgraph of the k-ary n-cube induced by the edges of P is a vertex-disj... Read More about Hamiltonian cycles through prescribed edges in k-ary n-cubes..

Color image edge detection based on quantity of color information and implementation on the GPU. (2011)
Presentation / Conference Contribution
Zhao, J., Xiang, Y., Dawson, L., & Stewart, I. (2011, December). Color image edge detection based on quantity of color information and implementation on the GPU. Presented at 23rd IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS'11., Dallas, USA

In this paper, we present a new method for quantifying color information so as to detect edges in color images. Our method uses the volume of a pixel in the HSI color space, allied with noise reduction, thresholding and edge thinning. We implement ou... Read More about Color image edge detection based on quantity of color information and implementation on the GPU..

On the approximation complexity hierarchy. (2011)
Presentation / Conference Contribution
Bordewich, M. (2010, September). On the approximation complexity hierarchy. Presented at 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool

This paper presents an extension of Ladner’s Theorem to the approximation complexity hierarchy. In 1975 Ladner proved that if P≠NP, then there exists an incomplete problem A which is neither in P nor NP-complete. Here we show that if RP≠NP, then ther... Read More about On the approximation complexity hierarchy..

The limits of tractability in Resolution-based propositional proof systems (2011)
Journal Article
Dantchev, S., & Martin, B. (2012). The limits of tractability in Resolution-based propositional proof systems. Annals of Pure and Applied Logic, 163(3), 656-668. https://doi.org/10.1016/j.apal.2011.11.001

We study classes of propositional contradictions based on the Least Number Principle (LNP) in the refutation system of Resolution and its generalisations with bounded conjunction, Res(k). We prove that any first-order sentence with no finite models t... Read More about The limits of tractability in Resolution-based propositional proof systems.

Online Regenerator Placement (2011)
Presentation / Conference Contribution
Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2011, December). Online Regenerator Placement. Presented at 15th International Conference on Principles of Distributed Systems (OPODIS), Toulouse, France

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one ligh... Read More about Online Regenerator Placement.