Complexity of dissociate set problems in some hereditary classes of graphs

MaRDI QIDQ2837376zbMATH OpenFDO

Authors Yury L. Orlovich, A. B. Dolgiĭ, Gerd Finke, V. S. Gordon, Frank Werner

Publication date 10 July 2013

Published in Doklady Natsional'noĭ Akademii Nauk Belarusi (Search for Journal in Brave)

zbMATH Keywords

maximal dissociation set problemNP-hardplanar bipartite graphsplanar line graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of dissociation set problems in graphs
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Relating dissociation, independence, and matchings
• Maximal and maximum dissociation sets in general and triangle-free graphs
• A bound on the dissociation number

Cited in

(6)

• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Maximal and maximum dissociation sets in general and triangle-free graphs
• The complexity of dissociation set problems in graphs
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• Uniformly dissociated graphs
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number

This page was built for publication: Complexity of dissociate set problems in some hereditary classes of graphs

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