D:\sbornik\...\Aritcle.DVI


Mathematical Problems of Computer Science 24, 2005, 62{75.

On Special M aximum M atchings Constr ucting¤

R a fa ye l R . K a m a lia n a n d V a h a n V . Mkr t c h ya n

Institute for Informatics and Automation Problems of NAS of RA,
Department of Informatics and Applied Mathematics, Yerevan State University,

e-mails rrkamalian@yahoo.com, vahanmkrtchyan2002yahoo.com

Abstract

For bipartite graphs the N P -completeness is proved for the problem of existence
of maximum matching which removal leads to a graph with given lower(upper) bound
for the cardinality of its maximum matching.

Refer ences

[1 ] H a r a r y F., \ Gr a p h Th e o r y" , A d d is o n -W e s le y, R e a d in g , MA , 1 9 6 9 .

[2 ] P a p a d im it r io u C.H ., S t e ig lit z K ., Co m b in a t o r ia l o p t im iz a t io n : A lg o r it h m s a n d Co m -
p le xit y, P R E N TICE -H A L L , IN C E n g le wo o d Cli®s , N e w Je r s e y,1 9 8 2 .

[3 ] Co o k S .A ., Th e c o m p le xit y o f t h e o r e m -p r o vin g p r o c e d u r e s , P r o c . 3 r d A n n . A CM S ym p .
On Th e o r y o f Co m p u t in g , A s s o c ia t io n fo r Co m p u t in g Ma c h in e r y, N e w Y o r k, 1 9 7 1 ,
p p .1 5 1 -1 5 8 .

[4 ] K a r p R . M., R e d u c ib ilit y a m o n g c o m b in a t o r ia l p r o b le m s , in R .E .Mille r a n d
J.W .Th a t c h e r s ( e d s ) , Co m p le xit y o f Co m p u t e r Co m p u t a t io n s , P le n u m P r e s s , N e w
Y o r k, 1 9 7 2 , p p .8 5 -1 0 3 .

[5 ] Ga r e y M.R . , Jo h n s o n D .S ., Co m p u t e r s a n d In t r a c t a b ilit y: A Gu id e t o t h e Th e o r y o f
N P -c o m p le t e n e s s . S a n Fr a n c is c o : W . H . Fr e e m a n & Co m p a n y, P u b lis h e r s , 1 9 7 9 .

[6 ] Ga r e y M.R ., Jo h n s o n D .S . a n d S t o c km e ye r L . \ S o m e s im p lī e d N P -c o m p le t e g r a p h
p r o b le m s " , Th e o r . Co m p u t . S c i 1 , N o . 3 , 2 3 7 -2 6 7 , 1 9 7 6 .

[7 ] E ve n S ., K a r iv O. A n O ( n2:5 ) A lg o r it h m fo r Ma xim u m Ma t c h in g in Ge n e r a l Gr a p h s ,
P r o c . S ixt e e n t h A n n u a l S ym p . On Fo u n d a t io n s o f Co m p u t e r S c ie n c e , B e r ke le y, Ca li-
fo r n ia : IE E E ( 1 9 7 5 ) ,1 0 0 -1 1 2 .

[8 ] Mic a li S ., V a z ir a n i V .V . A n O (
q
jV j ¢ jEj ) A lg o r it h m fo r Fin d in g Ma xim u m Ma t c h -

in g in Ge n e r a l Gr a p h s , P r o c . Twe n t y-̄ r s t A n n u a l S ym p o s iu m o n t h e Fo u n d a t io n s o f
Co m p u t e r S c ie n c e , L o n g B e a c h , Ca lifo r n ia : IE E E ( 1 9 8 0 ) ,1 7 -2 7 .

¤The work was partially supported by 04.10.31 Target Program of RA.

6 2



R. R. Kamalian, V. V. Mkrtchyan 6 3

гïáõÏ ïÇåÇ Ù³ùëÇÙ³É ½áõ·³ÏóáõÙÝ»ñÇ Ï³éáõóÙ³Ý Ù³ëÇÝ

è.è.ø³Ù³ÉÛ³Ý, ì.ì. ØÏñïãÛ³Ý

²Ù÷á÷áõÙ

ºñÏÏáÕÙ³ÝÇ ·ñ³ýÝ»ñÇ Ñ³Ù³ñ óáõÛó ¿ ïñí»É ³ÛÝåÇëÇ Ù³ùëÇÙ³É ½áõ·³ÏóÙ³Ý
ϳéáõóÙ³Ý ËݹñÇ NP-ÉñÇíáõÃÛáõÝÁ, áñÇ Ñ»é³óáõÙÇó ëï³óí³Í ·ñ³ýÇ Ù³ùëÇÙ³É
½áõ·³ÏóÙ³Ý Ñ½áñáõÃÛáõÝÁ µ³í³ñ³ñáõÙ ¿ ݳ˳å»ë ïñí³Í í»ñÇÝ (ëïáñÇÝ)
·Ý³Ñ³ï³Ï³ÝÇÝ: