Skip to main content

Solving the distance k-clique problem in 1-outerplanar graphs

Seminar by Alejandro Flores-Lamas (RHUL)

  • Date 14 Apr 2021
  • Time 3.00pm-4.00pm
  • Category Seminar

Solving the distance k-clique problem in 1-outerplanar graphs

Abstract: A clique is a subset of vertices from a simple graph G = (VG, EG) such that each vertex in the set is adjacent to all other vertices in it; in other words, any pair of such vertices are connected with just one edge. Similarly, a distance k-clique is a subset of vertices, from G, such that any pair of vertices in the set are connected with at most k-edges. In this sense, we can express a clique as a distance 1-clique set. A common formulation of these sets as a problem asks to find a Maximum Distance k-Clique, MDkC, from a given graph; i.e., the largest cardinality set. This problem is NP-hard in arbitrary graphs. In this talk, we address the MDkC problem in 1-outerplanar graphs; i.e., graphs that admit a drawing on the plane such that its edges only intersect at the vertices, and each vertex lies on the outer face of the drawing. Our approach to solving this problem was first finding an MDkC set in a tree. Then, we adapt this algorithm to run in 1-outerplanar graphs. The proposed algorithm uses dynamic programming, and it goes through two phases. In the first phase, the algorithm follows a postorder traversal on a tree decomposition of G to compute the size of an MDkC set. Then, during a second traversal (top-bottom) it identifies the vertices that belong to the set.

algorithms 2

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones.

Heading to university is exciting. Finding the right place to live will get you off to a good start.

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help.

Discover more about our 21 departments and schools.

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’.

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway.

Discover more about who we are today, and our vision for the future.

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today.

We’ve played a role in thousands of careers, some of them particularly remarkable.

Find about our decision-making processes and the people who lead and manage Royal Holloway today.