Search Constraints

Start Over
Filtering by: Creator Gudmundsson, Joachim Remove constraint Creator: Gudmundsson, Joachim Date Created 2006 Remove constraint Date Created: 2006

Search Results

  • On spanners of geometric graphs

    Resource Type:
    Conference Proceeding
    Creator:
    Smid, Michiel and Gudmundsson, Joachim
    Abstract:
    Given a connected geometric graph G, we consider the problem of constructing a t-spanner of G having the minimum number of edges. We prove that for every t with 1 1+1/t) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a t-spanner with O(tn1+2/(t+1)) edges. We also prove that the problem of deciding whether a given geometric graph contains a t-spanner with at most K edges is NP-hard. Previously, this NP-hardness result was only known for non-geometric graphs.
    Date Created:
    2006-01-01