Generalized maximal independence parameters for trees

Mercer, John (2001) Generalized maximal independence parameters for trees. Masters thesis, Memorial University of Newfoundland.

[img] [English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version
Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.

Download (7Mb)
  • [img] [English] PDF - Accepted Version
    Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.
    (Original Version)

Abstract

An independent set I ⊆ V of a graph G = (V.E) is said to be k-maximal if there does not exist two sets X and Y' such that X ⊆ I. Y ⊆ (V - I). |X| < k and (I - X) ∪ Y is an independent set of cardinality larger than |I|. This definition generalizes the traditional concept of maximality of independent sets. -- The problem of finding the smallest k-maximal set for a given graph is NP-hard for many simple classes of graphs, such as the class of bipartite graphs. Here we investigate the MINIMUM k-MAXIMAL INDEPENDENT SET (MIN k-MIS) problem for trees. We characterize the k-maximal independent sets for trees and we present an O(n³) time algorithm for the MIN k-MIS problem under this restriction. We will also show that we can test an independent set for k-maximality in O(n) time for trees.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/1287
Item ID: 1287
Additional Information: Bibliography: leaves 69-70.
Department(s): Science, Faculty of > Computer Science
Date: 2001
Date Type: Submission
Library of Congress Subject Heading: Trees (Graph theory)

Actions (login required)

View Item View Item

Downloads

Downloads per month over the past year

View more statistics