On the algorithmic complexity of twelve covering and independence parameters of graphs
From MaRDI portal
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.
Recommendations
Cites work
- A linear algorithm for the domination number of a tree
- A recurrence template for several parameters in series-parallel graphs
- Algorithms for generalized stability numbers of tree graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- An Algorithm for a Minimum Cover of a Graph
- An Analysis of the Greedy Heuristic for Independence Systems
- Approximation algorithms for NP-complete problems on planar graphs
- Chordal graphs and upper irredundance, upper domination and independence
- Clustering and domination in perfect graphs
- Dominating sets for split and bipartite graphs
- Dominating Sets in Chordal Graphs
- Dominating sets in perfect graphs
- Domination in permutation graphs
- Domination on Cocomparability Graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Double total domination of graphs
- Edge Dominating Sets in Graphs
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Gallai theorems for graphs, hypergraphs, and set systems
- Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices
- scientific article; zbMATH DE number 3648727 (Why is no real title available?)
- scientific article; zbMATH DE number 3154393 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3871413 (Why is no real title available?)
- scientific article; zbMATH DE number 3910441 (Why is no real title available?)
- scientific article; zbMATH DE number 3674114 (Why is no real title available?)
- scientific article; zbMATH DE number 3720947 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3603322 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- scientific article; zbMATH DE number 1124594 (Why is no real title available?)
- scientific article; zbMATH DE number 786167 (Why is no real title available?)
- scientific article; zbMATH DE number 861309 (Why is no real title available?)
- scientific article; zbMATH DE number 3432294 (Why is no real title available?)
- scientific article; zbMATH DE number 975351 (Why is no real title available?)
- scientific article; zbMATH DE number 3307328 (Why is no real title available?)
- Independent domination in chordal graphs
- Independent domination in regular graphs
- Independent sets in asteroidal triple-free graphs
- Matching theory
- Minimum Edge Dominating Sets
- Nordhaus-Gaddum inequalities for domination in graphs
- On a Nordhaus-Gaddum type problem for independent domination
- On approximating the minimum independent dominating set
- On Complementary Graphs
- On domination problems for permutation and other graphs
- On the product of upper irredundance numbers of a graph and its complement
- On total covering and matching of graphs
- On total covers of graphs
- On total matching numbers and total covering numbers of complementary graphs
- Parallel concepts in graph theory
- Paths, Trees, and Flowers
- Planar 3DM is NP-complete
- Some simplified NP-complete graph problems
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- The NP-completeness column: an ongoing guide
- The NP-completeness column: An ongoing guide
- The product of the independent domination numbers of a graph and its complement
- The Rectilinear Steiner Tree Problem is NP-Complete
- Total domination in graphs
- Total matchings and total coverings of graphs
- Total matchings and total coverings of threshold graphs
- Totally equimatchable graphs
- Two Bounds for the Domination Number of a Graph
Cited in
(24)- Vertex and edge covers with clustering properties: Complexity and algorithms
- Subset sum problems with digraph constraints
- On the complexity of the smallest grammar problem over fixed alphabets
- Extension and its price for the connected vertex cover problem
- Mixed domination and 2-independence in trees
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Small \(k\)-pyramids and the complexity of determining \(k\)
- Improved parameterized algorithms and kernels for mixed domination
- On complementary coverage of \({\Omega}_n(T)\)
- Total coloring and total matching: polyhedra and facets
- On the complexity landscape of the domination chain
- On the complexity of variations of mixed domination on graphs
- Signed mixed Roman domination numbers in graphs
- Independent dominating set problem revisited
- NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
- Weighted upper edge cover: complexity and approximability
- Signed mixed dominating functions in complete bipartite graphs
- The algorithmic complexity of mixed domination in graphs
- Upper and lower bounds on approximating weighted mixed domination
- scientific article; zbMATH DE number 7764100 (Why is no real title available?)
- Explicit construction of mixed dominating sets in generalized Petersen graphs
- On average sizes and enumeration of minimal edge covers
- The total matching polytope of complete bipartite graphs
- Total matching and subdeterminants
This page was built for publication: On the algorithmic complexity of twelve covering and independence parameters of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1283793)
