ՀՀ ԳԱԱ Զեկույցներ =Reports NAS RA

Об NP-полноте задачи существования локально-сбалансированного 2-разбиения двудольных графов G с Δ(G)=4 при расширенном определении окрестности вершины

Баликян, С. В. and Камалян, Р. Р. (2006) Об NP-полноте задачи существования локально-сбалансированного 2-разбиения двудольных графов G с Δ(G)=4 при расширенном определении окрестности вершины. ՀՀ ԳԱԱ Զեկույցներ, 106 (3). pp. 218-226. ISSN 0321-1339

[img]PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
197Kb

Abstract

Ապացուցված է 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.

Item Type:Article
Additional Information:Δ(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.
Uncontrolled Keywords:NP-полнота, локально-сбалансированный, разбиение, двудольный граф
Subjects:Q Science > QA Mathematics
ID Code:1465
Deposited By:NAS Reports
Deposited On:14 Oct 2011 10:07
Last Modified:13 Mar 2014 08:16

Repository Staff Only: item control page