On the algorithmic complexity of twelve covering and independence parameters of graphs
From MaRDI portal
Publication:1283793
DOI10.1016/S0166-218X(98)00147-4zbMath0922.05041OpenAlexW2008207969MaRDI QIDQ1283793
Publication date: 31 May 1999
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(98)00147-4
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (20)
Mixed domination and 2-independence in trees ⋮ Subset sum problems with digraph constraints ⋮ Signed mixed Roman domination numbers in graphs ⋮ NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Total coloring and total matching: polyhedra and facets ⋮ On the complexity of variations of mixed domination on graphs† ⋮ On complementary coverage of \({\Omega}_n(T)\) ⋮ Unnamed Item ⋮ Independent dominating set problem revisited ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ The algorithmic complexity of mixed domination in graphs ⋮ On the Complexity Landscape of the Domination Chain ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Improved parameterized algorithms and kernels for mixed domination ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Extension and its price for the connected vertex cover problem ⋮ Signed mixed dominating functions in complete bipartite graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- On approximating the minimum independent dominating set
- Domination, independent domination, and duality in strongly chordal graphs
- Dominating sets for split and bipartite graphs
- Gallai theorems for graphs, hypergraphs, and set systems
- Clustering and domination in perfect graphs
- Matching theory
- On domination problems for permutation and other graphs
- On the product of upper irredundance numbers of a graph and its complement
- Independent domination in chordal graphs
- Chordal graphs and upper irredundance, upper domination and independence
- Dominating sets in perfect graphs
- The product of the independent domination numbers of a graph and its complement
- On total covers of graphs
- A linear algorithm for the domination number of a tree
- Some simplified NP-complete graph problems
- On total matching numbers and total covering numbers of complementary graphs
- On total covering and matching of graphs
- Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices
- Parallel concepts in graph theory
- Total matchings and total coverings of threshold graphs
- A recurrence template for several parameters in series-parallel graphs
- Totally equimatchable graphs
- Double total domination of graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- On a Nordhaus-Gaddum type problem for independent domination
- Independent domination in regular graphs
- Nordhaus-Gaddum inequalities for domination in graphs
- Minimum Edge Dominating Sets
- Domination on Cocomparability Graphs
- On Complementary Graphs
- An Algorithm for a Minimum Cover of a Graph
- Domination in permutation graphs
- Planar 3DM is NP-complete
- The NP-completeness column: an ongoing guide
- Total domination in graphs
- Edge Dominating Sets in Graphs
- Dominating Sets in Chordal Graphs
- Total matchings and total coverings of graphs
- An Analysis of the Greedy Heuristic for Independence Systems
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Independent sets in asteroidal triple-free graphs
- Two Bounds for the Domination Number of a Graph
- Paths, Trees, and Flowers
- 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
- The NP-completeness column: An ongoing guide
This page was built for publication: On the algorithmic complexity of twelve covering and independence parameters of graphs
