Skip to main content

Research Repository

Advanced Search

Outputs (3164)

The longest path problem has a polynomial solution on interval graphs (2011)
Journal Article
Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2011). The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2), 320-341. https://doi.org/10.1007/s00453-010-9411-3

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamilton... Read More about The longest path problem has a polynomial solution on interval graphs.

The recognition of tolerance and bounded tolerance graphs (2011)
Journal Article
Mertzios, G., Sau, I., & Zaks, S. (2011). The recognition of tolerance and bounded tolerance graphs. SIAM Journal on Computing, 40(5), 1234-1257. https://doi.org/10.1137/090780328

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its num... Read More about The recognition of tolerance and bounded tolerance graphs.

Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption (2011)
Journal Article
Xiang, Y., & Stewart, I. (2011). Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption. IEEE Transactions on Parallel and Distributed Systems, 22(9), 1506-1513. https://doi.org/10.1109/tpds.2011.22

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 \geq 3, and k-pancyclic, if k \geq 5 is odd (these results are optimal). We go on to show that when k \geq 4... Read More about Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption.

Contracting planar graphs to contractions of triangulations (2011)
Journal Article
Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Contracting planar graphs to contractions of triangulations. Journal of discrete algorithms, 9(3), 299-306. https://doi.org/10.1016/j.jda.2011.03.010

For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, ther... Read More about Contracting planar graphs to contractions of triangulations.

On disconnected cuts and separators (2011)
Journal Article
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). On disconnected cuts and separators. Discrete Applied Mathematics, 159(13), 1345-1351. https://doi.org/10.1016/j.dam.2011.04.027

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V∖U)∪{u} is connec... Read More about On disconnected cuts and separators.

Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time (2011)
Presentation / Conference Contribution
Mertzios, G., & Bezáková, I. (2011, August). Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time. Presented at VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Bariloche, Argentina

The longest path problem asks for a path with the largest number of vertices in a given graph. The first polynomial time algorithm (with running time O(n4)) has been recently developed for interval graphs. Even though interval and circular-arc graphs... Read More about Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time.

Clustering based leaders' selection in multi-objective evolutionary algorithms (2011)
Presentation / Conference Contribution
Al Moubayed, N., Petrovski, A., & McCall, J. (2011, July). Clustering based leaders' selection in multi-objective evolutionary algorithms. Presented at Proceedings of the 13th annual conference companion on Genetic and evolutionary computation - GECCO '11, Dublin, Irland

Clustering-based Leaders Selection (CLS) is a novel leaders selection technique in multi-objective evolutionary algorithms. Clustering is applied on both the objective and solution spaces whereby each individual is assigned to two clusters; one in th... Read More about Clustering based leaders' selection in multi-objective evolutionary algorithms.

Multi-objective Optimisation of Cancer Chemotherapy using Smart PSO with Decomposition (2011)
Presentation / Conference Contribution
Al Moubayed, N., Petrovski, A., & McCall, J. (2011, April). Multi-objective Optimisation of Cancer Chemotherapy using Smart PSO with Decomposition. Presented at 2011 IEEE Symposium on Computational Intelligence in Multicriteria Decision-Making (MDCM), Paris, France

The paper presents a novel approach to optimising cancer chemotherapy with respect to conflicting treatment objectives aimed at reducing the number of cancerous cells and at limiting the amounts of anti-cancer drugs used. The approach is based on the... Read More about Multi-objective Optimisation of Cancer Chemotherapy using Smart PSO with Decomposition.

Vertex Splitting and the Recognition of Trapezoid Graphs (2011)
Journal Article
Mertzios, G., & Corneil, D. (2011). Vertex Splitting and the Recognition of Trapezoid Graphs. Discrete Applied Mathematics, 159(11), 1131-1147. https://doi.org/10.1016/j.dam.2011.03.023

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapez... Read More about Vertex Splitting and the Recognition of Trapezoid Graphs.