Հրապարակման մանրամասներ:

"ՀՀ ԳԱԱ Զեկույցներ" հանդեսը հիմնադրվել է 1944թ.: Լույս է տեսնում տարին 4 անգամ:

Ամսագրի կամ հրապարակման վերնագիր:

ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA

Հրապարակման ամսաթիվ:

2006

Հատոր:

106

Համար:

3

ISSN:

0321-1339

Պաշտոնական URL:

Լրացուցիչ տեղեկություն:

սեղմիր այստեղ կապին հետևելու համար

Այլ վերնագիր:

Δ(G)=4 պայմանին բավարարող G երկկողմանի գրաֆների լոկալ-հավասարակշռված 2-տրոհման գոյության խնդրի NP-լրիվության մասին` գագաթի շրջակայքի ընդլայնված սահմանման դեպքում / Ս. Վ. Բալիկյան, Ռ. Ռ. Քամալյան ։ On NP-completeness of the Problem of Existence of Locally-balanced 2-partition for Bipartite Graphs G with Δ(G)=4 under the Extended Definition of the Neighbourhood of a Vertex / S. V. Balikyan, R. R. Kamalian.

Աջակից(ներ):

Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)

Ծածկույթ:

218-226

Ամփոփում:

Ապացուցված է NP - լրիվությունը մի խնդրի, որի էությունը Δ(G)=4 պայմանին բավարարող G երկկողմանի գրաֆների գագաթների բազմության, V1 և V2 չհատվող ենթաբազմությունների այնպիսի տրոհման գոյությունը պարզելու մեջ է, երբ գրաֆի յուրաքանչյուր v գագաթի համար տեղի ունենա ||λ(υ)∩V1|­|λ(υ)∩V2||≤1 անհավասարությունը, որտեղ λ(υ)- ով նշանակված է այն գագաթների բազմությունը, որոնց հեռավորությունը υ-ից չի գերազանցում 1-ը: For bipartite graphs G with Δ(G)=4 the NP-completeness is shown for the problem of such partition of the set of vertices of G in two sets V1 and V2, which satisfies the condition ||λ(υ)∩V1|­|λ(υ)∩V2||≤1 for all vertices of G, where λ(υ)is the set of all vertices of G the distance of which from υ does not exceed 1.

Հրատարակության վայրը:

Երևան

Հրատարակիչ:

ՀՀ ԳԱԱ հրատ.

Ստեղծման ամսաթիվը:

2006-09-15

Ձևաչափ:

pdf

Նույնացուցիչ:

oai:arar.sci.am:46198

Դասիչ:

АЖ 144

Թվայնացում:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան

Բնօրինակի գտնվելու վայրը:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան