On the algorithmic complexity of twelve covering and independence parameters of graphs

On the algorithmic complexity of twelve covering and independence parameters of graphs

0.00 Avg rating0 Votes
Article ID: iaor20001710
Country: Netherlands
Volume: 91
Issue: 1/3
Start Page Number: 155
End Page Number: 175
Publication Date: Jan 1999
Journal: Discrete Applied Mathematics
Authors:
Keywords: computational analysis
Abstract:

The definitions of four previously studied parameters related to total coverings and total matchings of graphs can be restricted, thereby obaining eight parameters related to covering and independence, each of which has been studied previously in some form. Here we survey briefly results concerning total coverings and total matchings of graphs, and consider the aforementioned 12 coverings and independence parameters with regard to algorithmic complexity. We survey briefly known results for several graph classes, and obtain new NP-completeness results for the minimum total cover and maximum minimal total cover problems in planar graphs, the minimum maximal total matching problem in bipartite and chordal graphs, and the minimum independent dominating set problem in planar cubic graphs.

Reviews

Required fields are marked *. Your email address will not be published.