Skip to main content

Research Repository

Advanced Search

Outputs (323)

Graph editing to a fixed target
Presentation / Conference Contribution
Golovach, P., Paulusma, D., & Stewart, I. A. (2013, December). Graph editing to a fixed target. Presented at International Workshop on Combinatorial Algorithms, Rouen, France

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex di... Read More about Graph editing to a fixed target.

Hamiltonian cycles through prescribed edges in k-ary n-cubes.
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.
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..

Node-to-node disjoint paths in k-ary n-cubes with faulty edges.
Presentation / Conference Contribution
Xiang, Y., Stewart, I., & Madelaine, F. (2012, January). Node-to-node disjoint paths in k-ary n-cubes with faulty edges. Presented at 17th International Conference on Parallel and Distributed Systems, ICPADS'11., Tainan, Taiwan

Let u and v be any two given nodes in a k-ary n-cube Qnk with at most 2n-2 faulty edges. Suppose that the number of healthy links incident with u is no more than that of v, and denote this number by m. In this paper, we show that there are m mutually... Read More about Node-to-node disjoint paths in k-ary n-cubes with faulty edges..

Pancyclicity in faulty k-ary 2-cubes
Presentation / Conference Contribution
Xiang, Y., & Stewart, I. (2009, November). Pancyclicity in faulty k-ary 2-cubes. Presented at Proceedings of 21st International Conference on Parallel and Distributed Computing and Systems, PDCS'09., Cambridge, Massachusetts, USA

We prove that a k-ary 2-cube $Q_k^2$ with 3 faulty edges but where every vertex is incident with at least 2 healthy edges is bipancyclic, if k ≥ 3, and k-pancyclic, if k ≥ 5 is odd (these results are optimal).

Pancyclicity and panconnectivity in augmented k-ary n-cubes
Presentation / Conference Contribution
Xiang, Y., & Stewart, I. (2009, December). Pancyclicity and panconnectivity in augmented k-ary n-cubes. Presented at The Fifteenth International Conference on Parallel and Distributed Systems : ICPADS'09, Shenzhen, China

The augmented k-ary n-cube AQ_{n,k} is a recently proposed interconnection network that incorporates an extension of a k-ary n-cube Q_n^k inspired by the extension of a hypercube Q_n to the augmented hypercube AQ_n (as developed by Choudom and Sunita... Read More about Pancyclicity and panconnectivity in augmented k-ary n-cubes.

Frameworks for logically classifying polynomial-time optimisation problems
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 general algorithm for detecting faults under the comparison diagnosis model
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.

The computational complexity of the parallel knock-out problem
Presentation / Conference Contribution
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006, March). The computational complexity of the parallel knock-out problem. Presented at 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile

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.

A generic greedy algorithm, partially-ordered graphs and NP-completeness
Presentation / Conference Contribution
Puricella, A., & Stewart, I. (2001, June). A generic greedy algorithm, partially-ordered graphs and NP-completeness. Presented at 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Rostock, Germany

Let π be any fixed polynomial-time testable, non-trivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possi... Read More about A generic greedy algorithm, partially-ordered graphs and NP-completeness.

Cross-chain Transaction Validation using Lock-and-Key Method for Multi-System Blockchain
Presentation / Conference Contribution
Kumar, G., Lahiri, S., Dua, A., & Aujla, G. S. (2023, May). Cross-chain Transaction Validation using Lock-and-Key Method for Multi-System Blockchain. Presented at 2023 IEEE International Conference on Communications Workshops (ICC Workshops), Rome, Italy

Blockchains have profoundly impacted finance and administration, but there are several issues with the current blockchain platforms, including a lack of system interoperability. Currently used blockchain application platforms only work within their n... Read More about Cross-chain Transaction Validation using Lock-and-Key Method for Multi-System Blockchain.

Time- and Communication-Efficient Overlay Network Construction via Gossip
Presentation / Conference Contribution
Dufoulon, F., Moorman, M., Moses Jr., W. K., & Pandurangan, G. (2024, January). Time- and Communication-Efficient Overlay Network Construction via Gossip. Presented at ITCS 2024: Innovations in Theoretical Computer Science (ITCS), Berkeley, California

Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd
Presentation / Conference Contribution
Moses Jr., W. K., & Redlich, A. (2024, January). Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd. Presented at 25th International Conference on Distributed Computing and Networking, Chennai, India

In this paper, we look at and expand the problems of dispersion and Byzantine dispersion of mobile robots on a graph, introduced by Augustine and Moses Jr. [ICDCN 2018] and by Molla, Mondal, and Moses Jr. [ALGOSENSORS 2020], respectively, to graphs w... Read More about Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd.

Awake Complexity of Distributed Minimum Spanning Tree
Presentation / Conference Contribution
Augustine, J., Moses Jr, W. K., & Pandurangan, G. (2024, May). Awake Complexity of Distributed Minimum Spanning Tree. Presented at SIROCCO 2024: 31st International Colloquium On Structural Information and Communication Complexity, Vietri sul Mare, Salerno, Italy

The \emph{awake complexity} of a distributed algorithm measures the number of rounds in which a node is awake. When a node is not awake, it is {\em sleeping} and does not do any computation or communication and spends very little resources.
Reduci... Read More about Awake Complexity of Distributed Minimum Spanning Tree.

Towards Communication-Efficient Peer-to-Peer Networks
Presentation / Conference Contribution
Hourani, K., Moses Jr., W. K., & Pandurangan, G. (2024, September). Towards Communication-Efficient Peer-to-Peer Networks. Presented at 32nd Annual European Symposium on Algorithms (ESA 2024), Egham, United Kingdom

We focus on designing Peer-to-Peer (P2P) networks that enable efficient communication. Over the last two decades, there has been substantial algorithmic research on distributed protocols for building P2P networks with various desirable properties suc... Read More about Towards Communication-Efficient Peer-to-Peer Networks.