Yong Gao

  1. A note on the hardness of graph diameter augmentation problems.

    Authors: James Nastos, Yong Gao
    Subjects: Discrete Mathematics
    Abstract

    A graph has \emph{diameter} D if every pair of vertices are connected by a
    path of at most D edges. The Diameter-D Augmentation problem asks how to add
    the a number of edges to a graph in order to make the resulting graph have
    diameter D. It was previously known that this problem is NP-hard \cite{GJ},
    even in the D=2 case. In this note, we give a simpler reduction to arrive at
    this fact and show that this problem is W[2]-hard.

Syndicate content