On the algorithmic complexity of twelve covering and independence parameters of graphs
type: Item
instance of: scholarly article
title: On the algorithmic complexity of twelve covering and independence parameters of graphs
zbMATH Open document ID: 0922.05041
DOI: 10.1016/S0166-218X(98)00147-4
author: David F. Manlove
published in: Discrete Applied Mathematics
publication date: 1999-05-31T00:00:00Z
review text: Twelve parameters related to covering of vertices and/or edges by vertices and/or edges, and to independence, are identified in a uniform framework. Known results on these parameters are surveyed, focusing on complexity results. Several new NP-completeness results are established.
reviewed by: Charles J. Colbourn
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1271071
zbMATH Keywords: edge covering
zbMATH Keywords: vertex covering
zbMATH Keywords: matching
zbMATH Keywords: independence
MaRDI profile type: Publication
cites work: Total matchings and total coverings of graphs
cites work: On total covers of graphs
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Q3941433
cites work: Dominating sets for split and bipartite graphs
cites work: Q3206969
cites work: Dominating Sets in Chordal Graphs
cites work: The algorithmic use of hypertree structure and maximum neighbourhood orderings
cites work: On domination problems for permutation and other graphs
cites work: Independent sets in asteroidal triple-free graphs
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: Q5183522
cites work: Total domination in graphs
cites work: The product of the independent domination numbers of a graph and its complement
cites work: On a Nordhaus-Gaddum type problem for independent domination
cites work: A linear algorithm for the domination number of a tree
cites work: Gallai theorems for graphs, hypergraphs, and set systems
cites work: On the product of upper irredundance numbers of a graph and its complement
cites work: Clustering and domination in perfect graphs
cites work: Dominating sets in perfect graphs
cites work: Algorithms for generalized stability numbers of tree graphs
cites work: Planar 3DM is NP-complete
cites work: Paths, Trees, and Flowers
cites work: Q5284020
cites work: On total matching numbers and total covering numbers of complementary graphs
cites work: Independent domination in chordal graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Domination in permutation graphs
cites work: Q3270978
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Double total domination of graphs
cites work: Q4842744
cites work: Q3328583
cites work: A recurrence template for several parameters in series-parallel graphs
cites work: Q5588430
cites work: Parallel concepts in graph theory
cites work: Nordhaus-Gaddum inequalities for domination in graphs
cites work: Independent domination in regular graphs
cites work: Q4368729
cites work: Q4368728
cites work: Q4871033
cites work: Q3338291
cites work: Minimum Edge Dominating Sets
cites work: On approximating the minimum independent dominating set
cites work: Chordal graphs and upper irredundance, upper domination and independence
cites work: The NP-completeness column: An ongoing guide
cites work: The NP-completeness column: an ongoing guide
cites work: An Analysis of the Greedy Heuristic for Independence Systems
cites work: Domination on Cocomparability Graphs
cites work: Matching theory
cites work: Q3910551
cites work: On total covering and matching of graphs
cites work: Q3870917
cites work: Two Bounds for the Domination Number of a Graph
cites work: Q4168642
cites work: On Complementary Graphs
cites work: An Algorithm for a Minimum Cover of a Graph

On the algorithmic complexity of twelve covering and independence parameters of graphs (cites work)
cites work: Total matchings and total coverings of threshold graphs

On the algorithmic complexity of twelve covering and independence parameters of graphs (cites work)
cites work: Q3688433

On the algorithmic complexity of twelve covering and independence parameters of graphs (cites work)
cites work: Q4378622

On the algorithmic complexity of twelve covering and independence parameters of graphs (cites work)
cites work: Edge domination on bipartite permutation graphs and cotriangulated graphs

On the algorithmic complexity of twelve covering and independence parameters of graphs (cites work)
cites work: Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices

On the algorithmic complexity of twelve covering and independence parameters of graphs (cites work)
cites work: Totally equimatchable graphs

On the algorithmic complexity of twelve covering and independence parameters of graphs (cites work)
cites work: Edge Dominating Sets in Graphs

On the algorithmic complexity of twelve covering and independence parameters of graphs (full work available at URL)
full work available at URL: s0166-218x(98)00147-4

On the algorithmic complexity of twelve covering and independence parameters of graphs (OpenAlex ID)
OpenAlex ID: W2008207969