Generalized maximal independence parameters for trees

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

[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 (8MB) [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.

Actions (login required)

View Item