The hardness of the independence and matching clutter of a graph

• Autorzy: Hambardzumyan S. , Mkrtchyan V. V. , Musoyan V. L. , Sargsyan H.

Identyfikatory

DOI

10.7494/OpMath.2016.36.3.375

• Języki publikacji: EN

Abstrakty

EN

A clutter (or antichain or Sperner family) L is a pair (V, E), where V is a finite set and E is a family of subsets of V none of which is a subset of another. Usually, the elements of V are called vertices of L, and the elements of E are called edges of L. A subset se of an edge e of a clutter is called recognizing for e, if se is not a subset of another edge. The hardness of an edge e of a clutter is the ratio of the size of e's smallest recognizing subset to the size of e. The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.

Słowa kluczowe

EN

clutter; hardness; independent set; maximal independent set; matching; maximal matching

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2016
• Tom: Vol. 36, no. 3
• Strony: 375--397
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Hambardzumyan S.

• Department of Informatics and Applied Mathematics Yerevan State University, Yerevan, 0025, Armenia

autor

Mkrtchyan V. V.

• Institute for Informatics and Automation Problems National Academy of Sciences of Republic of Armenia 0014, Armenia

autor

Musoyan V. L.

• Stanford University Computer Science Department Stanford, CA 94305, USA

autor

Sargsyan H.

• Department of Informatics and Applied Mathematics Yerevan State University, Yerevan, 0025, Armenia

Bibliografia

• [1] J.C. Claussen, Offdiagonal complexity: A computationally quick complexity measure for graphs and networks, Physica A 375 (2007), 365-373.
• [2] G. Cornuejols, Combinatorial Optimization: Packing and Covering, SIAM (January, 2001).
• [3] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.
• [4] S. Jukna, On graph complexity, ECCC Report, No. 5, 2004.
• [5] L. Lovasz, M.D. Plummer, Matching theory, Ann. Discrete Math. 29 (1986).
• [6] D.P. Sumner, Randomly matchable graphs, J. Graph Theory 3 (1979), 183-186.
• [7] D.B. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, 1996.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.