The complexity of dissociation set problems in graphs

DOI10.1016/J.DAM.2011.04.023zbMATH Open1223.68058OpenAlexW2131265210WikidataQ57633866 ScholiaQ57633866MaRDI QIDQ2275943FDOQ2275943

Authors: Yury L. Orlovich, Gerd Finke, Frank Werner, Alexandre Dolgui, V. S. Gordon 

Publication date: 10 August 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.04.023

Recommendations

• Complexity of dissociate set problems in some hereditary classes of graphs
• Complexity results for the proper disconnection of graphs
• Complexity of a disjoint matching problem on bipartite graphs
• Complexity of graph partition problems
• The complexity of unions of disjoint sets
• The Complexity of Unions of Disjoint Sets
• Set graphs. II. Complexity of set graph recognition and similar problems
• Computational complexity of covering disconnected multigraphs
• The complexity of some problems on maximal independent sets in graphs
• On the distributional complexity of disjointness

zbMATH Keywords

computational complexityforbidden induced subgraphapproximabilitydissociation set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Graph theory
• Title not available (Why is that?)
• On the Complexity of General Graph Factor Problems
• Graph Classes: A Survey
• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Title not available (Why is that?)
• A New Algorithm for Generating All the Maximal Independent Sets
• Title not available (Why is that?)
• On the completeness of a generalized matching problem
• The complexity of theorem-proving procedures
• Approximating the minimum maximal independence number
• On approximating the minimum independent dominating set
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some results on graphs without long induced paths
• On maximal independent sets of vertices in claw-free graphs
• Induced matchings
• On maximum induced matchings in bipartite graphs
• HAMILTONian circuits in chordal bipartite graphs
• Node-Deletion Problems on Bipartite Graphs
• Title not available (Why is that?)
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Weakly triangulated graphs
• Domination in convex and chordal bipartite graphs
• Stability number of bull- and chair-free graphs
• Title not available (Why is that?)
• Induced matchings in asteroidal triple-free graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Perfect Elimination and Chordal Bipartite Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• The complexity of restricted spanning tree problems
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• NP-completeness of some generalizations of the maximum matching problem
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Algorithms for weakly triangulated graphs
• The graphs with maximum induced matching and maximum matching the same size
• Independent Sets in Asteroidal Triple-Free Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• On the approximability of the maximum induced matching problem
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Induced matchings in intersection graphs.
• Finding a maximum induced matching in weakly chordal graphs
• On graphs with polynomially solvable maximum-weight clique problem
• Bipartite Domination and Simultaneous Matroid Covers
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Approximability results for the maximum and minimum maximal induced matching problems
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Optimizing weakly triangulated graphs
• On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
• Title not available (Why is that?)
• Algorithms – ESA 2004
• Computing independent sets in graphs with large girth
• Reductions, completeness and the hardness of approximability
• Improper coloring of unit disk graphs
• Independent packings in structured graphs
• Title not available (Why is that?)
• Irredundancy in circular arc graphs
• Title not available (Why is that?)

Cited In (46)

• The maximum number of maximum dissociation sets in trees
• Title not available (Why is that?)
• Partitioning a graph into small pieces with applications to path transversal
• Maximum dissociation sets in subcubic trees
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• Treewidth versus clique number. II: Tree-independence number
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• Hitting subgraphs in \(P_4\)-tidy graphs
• Approximation algorithm for minimum connected 3-path vertex cover
• Enumerating maximal dissociation sets in three classes of grid graphs
• The \(k\)-path vertex cover of rooted product graphs
• Improved approximation algorithms for path vertex covers in regular graphs
• 3-path vertex cover and dissociation number of hexagonal graphs
• On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
• Solving a special case of the P conjecture using dependency graphs with dissolution
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• A bound on the dissociation number
• Approximating bounded degree deletion via matroid matching
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• The maximum number of maximum generalized 4-independent sets in trees
• The maximum weight \((\{K_1,K_2\},k,l)\)-packing problem in a graph
• Approximating partially bounded degree deletion on directed graphs
• Maximal and maximum dissociation sets in general and triangle-free graphs
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Extremal vertex-degree function index with given order and dissociation number
• On spectral extrema of graphs with given order and dissociation number
• Complexity of dissociate set problems in some hereditary classes of graphs
• On the vertex \(k\)-path cover
• Minimum number of maximal dissociation sets in trees
• Relating the independence number and the dissociation number
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• On the \(A_\alpha\)-index of graphs with given order and dissociation number
• Uniformly dissociated graphs
• Relating dissociation, independence, and matchings
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Kernels for packing and covering problems
• A faster FPT algorithm for 3-path vertex cover
• A \(5k\)-vertex kernel for 3-path vertex cover
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• New results on directed edge dominating set

This page was built for publication: The complexity of dissociation set problems in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275943)