CompletedCourse work · Advanced Algorithmic Graph Theory

A Review of Approximation Algorithms for the Maximum Weighted Internal Spanning Tree Problem

Jahid Hasan, Abdul Wazed Rifat, Dr. Md. Saidur Rahman2 resources

Abstract

The Maximum Weighted Internal Spanning Tree (MaxWIST) problem is a well- known NP-hard problem in Graph Theory. Given a vertex-weighted connected graph G = (V, E) with n vertices, the goal is to find a spanning tree T that maximizes the sum of its internal vertices. This problem has significant applications in the real world such as network design, circuit layout, database systems, and social network analysis. This review paper is focused on recent advances in approximation algorithms for the MaxWIST problem, especially for d-regular graphs. I summarize the key study that provides a novel approximation algorithm for d-regular graphs with a tighter upper bound, and I also summarize the results on different types of graph subdivisions.

Resources

  • ReviewPaperPDF
  • Approximation Algorithms for MaxWIST in Regular GraphsSlides

    Slide decks (.pptx) can’t be previewed inline.

Research & Projects