Dissociation number

Dissociation number

In the mathematical discipline of graph theory, a subset of vertices in a graph G is called dissociation if it induces a subgraph with maximum degree 1. The number of vertices in a maximum cardinality dissociation set in G is called the dissociation number of G, denoted by diss(G). The problem of computing diss(G) (dissociation number problem) was firstly studied by Yannakakis [1][2], where it was proved to be NP-hard in the class of bipartite and planar graphs.

Notes

  1. ^ Yannakakis 1981
  2. ^ Papadimitriou and Yannakakis 1982

References

  • Yannakakis, Mihalis (1981). "Node-Deletion Problems on Bipartite Graphs". SIAM J. Comput. (2): 310–327. doi:10.1137/0210022. 
  • Papadimitriou, Christos H.; Yannakakis, Mihalis (1982). "The complexity of restricted spanning tree problems". J. ACM 29 (2): 285–309. doi:10.1145/322307.322309. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Dissociation (chemistry) — For other uses, see dissociation (psychology) and dissociation (neuropsychology). Dissociation in chemistry and biochemistry is a general process in which ionic compounds (complexes, or salts) separate or split into smaller particles, ions, or… …   Wikipedia

  • Dissociation constant — Kd redirects here. For other uses, see KD (disambiguation). In chemistry, biochemistry, and pharmacology, a dissociation constant is a specific type of equilibrium constant that measures the propensity of a larger object to separate (dissociate)… …   Wikipedia

  • dissociation model of hallucinatory experience —    The term dissociation model is indebted to the Latin words dis (apart, away from each other) and associare (to gather, to unite). It refers to a hypothetical model introduced in or shortly before 1894 by the German hallucinations researcher… …   Dictionary of Hallucinations

  • Acid dissociation constant — Acetic acid, a weak acid, donates a proton (hydrogen ion, high …   Wikipedia

  • Mach number — (mathrm{Ma} or M) (generally pronEng|ˈmɑːk, sometimes IPA|/ˈmɑːx/ or IPA|/ˈmæk/) is the speed of an object moving through air, or any fluid substance, divided by the speed of sound as it is in that substance. It is commonly used to represent an… …   Wikipedia

  • degree of dissociation — noun (chem) The fraction of the total number of molecules that are dissociated • • • Main Entry: ↑degree …   Useful english dictionary

  • Dissociative identity disorder — Not to be confused with Dissocial personality disorder. Split personality redirects here. For other uses, see Split personality (disambiguation). Dissociative Identity Disorder Classification and external resources ICD 10 F44.8 …   Wikipedia

  • acid–base reaction — ▪ chemistry Introduction       a type of chemical process typified by the exchange of one or more hydrogen ions, H+, between species that may be neutral (molecules, such as water, H2O; or acetic acid, CH3CO2H) or electrically charged (ions, such… …   Universalium

  • radiation — radiational, adj. /ray dee ay sheuhn/, n. 1. Physics. a. the process in which energy is emitted as particles or waves. b. the complete process in which energy is emitted by one body, transmitted through an intervening medium or space, and… …   Universalium

  • coordination compound — Chem. complex (def. 10). Also called coordination complex. * * * ▪ chemistry Introduction  any of a class of substances with chemical structures in which a central metal atom is surrounded by nonmetal atoms or groups of atoms, called ligands… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”