تقسيم الرسم البياني

الموسوعة الحرة

في الرياضيات، يُعرَّف تقسيم الرسم البياني بأنه اختزال الرسم البياني إلى رسم بياني أصغر بتقسيم مجموعة عقده إلى مجموعات حصرية متبادلة. تُنتج حواف الرسم البياني الأصلي التي تتقاطع بين المجموعات حوافًا في الرسم البياني المُقسَّم. إذا كان عدد الحواف الناتجة صغيرًا مقارنةً بالرسم البياني الأصلي، فقد يكون الرسم البياني المُقسَّم أنسب للتحليل وحل المشكلات من الرسم البياني الأصلي. يُعدّ إيجاد تقسيم يُبسِّط تحليل الرسم البياني مشكلةً صعبة، لكنها تُستخدم في الحوسبة العلمية، وتصميم دوائر VLSI ، وجدولة المهام في الحواسيب متعددة المعالجات، وغيرها. [ 1 ] اكتسبت مشكلة تقسيم الرسم البياني أهميةً مؤخرًا نظرًا لتطبيقها في تجميع البيانات واكتشاف الزمر في الشبكات الاجتماعية والمرضية والبيولوجية. للاطلاع على دراسة استقصائية حول الاتجاهات الحديثة في الأساليب الحسابية وتطبيقاتها، انظر Buluc et al. (2013) . [ 2 ] من الأمثلة الشائعة على تقسيم الرسم البياني مشكلتا القطع الأدنى والقطع الأقصى .

تعقيد المشكلة

تُصنَّف مسائل تقسيم الرسوم البيانية عادةً ضمن فئة المسائل الصعبة من نوع NP . وتُستنتج حلول هذه المسائل عمومًا باستخدام الطرق الاستدلالية وخوارزميات التقريب. [ 3 ] ومع ذلك، يمكن إثبات أن مسألة تقسيم الرسوم البيانية المنتظمة أو المتوازنة هي مسألة كاملة من نوع NP عند تقريبها ضمن أي عامل محدود. [ 1 ] حتى بالنسبة لأنواع الرسوم البيانية الخاصة كالأشجار والشبكات، لا توجد خوارزميات تقريب معقولة، [ 4 ] إلا إذا كانت P=NP . تُعدّ الشبكات حالةً مثيرةً للاهتمام بشكل خاص لأنها تُحاكي الرسوم البيانية الناتجة عن محاكاة نموذج العناصر المحدودة (FEM) . عندما لا يقتصر التقريب على عدد الحواف بين المكونات فحسب، بل يشمل أيضًا أحجام المكونات، يمكن إثبات عدم وجود خوارزميات معقولة متعددة الحدود بالكامل لهذه الرسوم البيانية. [ 4 ]

مشكلة

لنفترض وجود رسم بياني G = ( V , E )، حيث V تمثل مجموعة الرؤوس n و E تمثل مجموعة الحواف. في مسألة التقسيم المتوازن ( k , v )، يكون الهدف هو تقسيم G إلى k مكونات بحجم لا يتجاوز v · ( n / k )، مع تقليل سعة الحواف بين المكونات المنفصلة. [ 1 ] كذلك، بمعلومية G وعدد صحيح k > 1، يتم تقسيم V إلى k أجزاء (مجموعات جزئية) V1 , V2 , ... , Vk بحيث تكون الأجزاء منفصلة ومتساوية في الحجم، ويتم تقليل عدد الحواف ذات النهايات في أجزاء مختلفة. نوقشت مسائل التقسيم هذه في الأدبيات كطرق تقريب ثنائية المعايير أو طرق زيادة الموارد. أحد التوسعات الشائعة هو الرسوم البيانية الفائقة ، حيث يمكن للحافة أن تربط أكثر من رأسين. لا يتم قطع الحافة الفائقة إذا كانت جميع الرؤوس في قسم واحد، ويتم قطعها مرة واحدة فقط في غير ذلك، بغض النظر عن عدد الرؤوس على كل جانب. يُعد هذا الاستخدام شائعًا في أتمتة التصميم الإلكتروني .

تحليل

في مسألة تقسيم متوازنة محددة ( k , 1  + ε )، نسعى لإيجاد تقسيم بأقل تكلفة للشبكة G إلى k مكونات، بحيث يحتوي كل مكون على (1 + ε )·( n / k ) عقدة كحد أقصى. نقارن تكلفة خوارزمية التقريب هذه بتكلفة القطع ( k , 1)، حيث يجب أن يحتوي كل مكون من المكونات k على نفس عدد العقد ( n / k )، مما يجعلها مسألة أكثر تقييدًا.   

الأعلىأنا|Vأنا|≤(1+ε)⌈|V|ك⌉.{\displaystyle \max _{i}|V_{i}|\leq (1+\varepsilon )\left\lceil {\frac {|V|}{k}}\right\rceil .}

نعلم مسبقًا أن القطع (2,1) هو مسألة تقسيم ثنائي أدنى، وهي مسألة NP-كاملة. [5] بعد ذلك، نقوم بتقييم مسألة تقسيم ثلاثي حيث n = 3k ، وهي مسألة محدودة أيضًا  في  زمن متعدد الحدود. [ 1 ] الآن، إذا افترضنا وجود خوارزمية تقريب محدودة للتقسيم المتوازن ( k , 1)، فإما أن يتم حل مسألة التقسيم الثلاثي باستخدام التقسيم المتوازن ( k , 1) في G ، أو لا يمكن حلها. إذا أمكن حل مسألة التقسيم الثلاثي، فسيتم حل مسألة التقسيم المتوازن ( k , 1) في G دون قطع أي حافة. ​​أما إذا تعذر حل مسألة التقسيم الثلاثي، فإن التقسيم الأمثل المتوازن ( k , 1) في G سيقطع حافة واحدة على الأقل. يجب على خوارزمية التقريب ذات عامل التقريب المحدود التمييز بين هاتين الحالتين. وبالتالي، يمكنها حل مشكلة التقسيم الثلاثي، وهو ما يُعد تناقضًا بافتراض أن P = NP . ومن ثم، يتضح أنه لا توجد خوارزمية تقريبية ذات زمن متعدد الحدود بمعامل تقريب محدود لمشكلة التقسيم المتوازن ( k ,1) إلا إذا كانت P = NP . [ 1 ]      

تنص نظرية الفاصل المستوي على أنه يمكن تقسيم أي رسم بياني مستوي ذي n رأس إلى أجزاء متساوية تقريبًا بإزالة O( √n ) رأسًا. هذا ليس تقسيمًا بالمعنى المذكور أعلاه، لأن مجموعة التقسيم تتكون من رؤوس وليس من حواف. ومع ذلك، تشير النتيجة نفسها أيضًا إلى أن كل رسم بياني مستوي ذي درجة محدودة له قطع متوازن مع O( √n ) حافة.

أساليب تقسيم الرسم البياني

نظرًا لصعوبة تجزئة الرسوم البيانية، تعتمد الحلول العملية على أساليب استدلالية. يوجد نوعان رئيسيان من هذه الأساليب: المحلية والعالمية. من أشهر الأساليب المحلية خوارزمية كيرنيغان-لين وخوارزمية فيدوتشيا-ماثيسيس ، اللتان كانتا أول خوارزميات فعالة للقطع الثنائي باستخدام استراتيجيات البحث المحلي. يتمثل عيبهما الرئيسي في التجزئة الأولية العشوائية لمجموعة الرؤوس، مما قد يؤثر على جودة الحل النهائي. أما الأساليب العالمية فتعتمد على خصائص الرسم البياني بأكمله ولا تعتمد على تجزئة أولية عشوائية. المثال الأكثر شيوعًا هو التجزئة الطيفية، حيث تُشتق التجزئة من المتجهات الذاتية التقريبية لمصفوفة التجاور، أو التجميع الطيفي الذي يُجمّع رؤوس الرسم البياني باستخدام تحليل القيم الذاتية لمصفوفة لابلاس للرسم البياني .

الأساليب متعددة المستويات

تعمل خوارزمية تقسيم الرسوم البيانية متعددة المستويات بتطبيق مرحلة واحدة أو أكثر. تُقلل كل مرحلة حجم الرسم البياني عن طريق دمج الرؤوس والحواف، ثم تُقسّم الرسم البياني المُصغّر، ثم تُعيد رسم هذا التقسيم للرسم البياني الأصلي وتُحسّنه. [ 6 ] يمكن تطبيق مجموعة واسعة من طرق التقسيم والتحسين ضمن المخطط متعدد المستويات. في كثير من الحالات، يُمكن لهذا النهج أن يُحقق أوقات تنفيذ سريعة ونتائج عالية الجودة. من الأمثلة الشائعة على هذا النهج METIS [ 7 ] ، وهو مُقسّم للرسوم البيانية، وhMETIS، وهو المُقسّم المُقابل للرسوم البيانية الفائقة. [ 8 ] ثمة نهج بديل نشأ من [ 9 ] وتم تنفيذه، على سبيل المثال، في مكتبة scikit-learn ، وهو التجميع الطيفي مع تحديد التقسيم من المتجهات الذاتية لمصفوفة لابلاس للرسم البياني الأصلي المحسوبة بواسطة مُحلّل LOBPCG مع التكييف المُسبق متعدد الشبكات .

التقسيم الطيفي والتقسيم الطيفي الثنائي

بالنظر إلى رسم بيانيجي=(V،هـ){\displaystyle G=(V,E)}باستخدام مصفوفة التجاورأ{\displaystyle A}، حيث يكون المدخلأأناج{\displaystyle A_{ij}}يشير ذلك إلى وجود حافة بين العقدةأنا{\displaystyle i}وج{\displaystyle j}، ومصفوفة الدرجاتد{\displaystyle D}وهي مصفوفة قطرية ، حيث كل عنصر قطري في صفأنا{\displaystyle i}،دأناأنا{\displaystyle d_{ii}}، يمثل درجة العقدةأنا{\displaystyle i}مصفوفة لابلاسل{\displaystyle L}يُعرَّف بأنهل=د-أ{\displaystyle L=DA}الآن، تجزئة بنسبة القطع للرسم البيانيجي=(V،هـ){\displaystyle G=(V,E)}يُعرَّف بأنه تقسيم لـV{\displaystyle V}إلى أجزاء منفصلةيو{\displaystyle U}، ودبليو{\displaystyle W}، مما يقلل النسبة

|هـ(جي)∩(يو×دبليو)||يو|⋅|دبليو|{\displaystyle {\frac {|E(G)\cap (U\times W)|}{|U|\cdot |W|}}}

نسبة عدد الحواف التي تعبر هذا القطع فعليًا إلى عدد أزواج الرؤوس التي يمكن أن تدعم هذه الحواف. يمكن تبرير تقسيم الرسم البياني الطيفي [ 10 ] بالقياس إلى تقسيم وتر مهتز أو نظام كتلة-نابض، ويمكن توسيعه بالمثل ليشمل حالة الأوزان السالبة للرسم البياني. [ 11 ]

القيمة الذاتية والمتجه الذاتي لفيدلر

في مثل هذا السيناريو، تكون القيمة الذاتية الثانية الأصغر (λ2{\displaystyle \lambda _{2}}) لل{\displaystyle L}، مما ينتج عنه حد أدنى للتكلفة المثلى (ج{\displaystyle c}) من تجزئة القطع النسبي معج≥λ2ن{\displaystyle c\geq {\frac {\lambda _{2}}{n}}}المتجه الذاتي (V2{\displaystyle V_{2}}) المقابل لـλ2{\displaystyle \lambda _{2}}يُقسّم متجه فيدلر ، المعروف أيضًا باسم متجه فيدلر ، الرسم البياني إلى مجموعتين فقط بناءً على إشارة العنصر المقابل في المتجه . ويمكن تقسيم الرسم البياني إلى عدد أكبر من المجموعات عن طريق التقسيم المزدوج المتكرر أو باستخدام متجهات ذاتية متعددة تتوافق مع أصغر القيم الذاتية. [ 12 ] توضح الأمثلة في الشكلين 1 و2 أسلوب التقسيم المزدوج الطيفي.

الشكل 1: تم تحليل الرسم البياني G  =  (5,4) لتقسيم الطيف إلى نصفين. يؤدي التركيب الخطي لأصغر متجهين ذاتيين إلى [1 1 1 1 1]' بقيمة ذاتية تساوي  صفرًا  .
الشكل 2: يوضح الرسم البياني G  =  (5,5) أن متجه فيدلر باللون الأحمر يقسم الرسم البياني إلى مجموعتين، إحداهما تحتوي على رؤوس {1,2,3} ذات مدخلات موجبة في فضاء المتجهات، والمجموعة الأخرى تحتوي على رؤوس {4,5} ذات مدخلات سالبة في فضاء المتجهات.

النمطية والقطع النسبي

مع ذلك، تفشل خوارزمية تقسيم القطع الأدنى عندما يكون عدد المجموعات المراد تقسيمها، أو أحجام التقسيمات، غير معروف. على سبيل المثال، يؤدي تحسين حجم القطع لأحجام المجموعات الحرة إلى وضع جميع الرؤوس في نفس المجموعة. بالإضافة إلى ذلك، قد يكون تقليل حجم القطع غير مناسب، لأن التقسيم الجيد لا يقتصر على التقسيم الذي يحتوي على عدد قليل من الحواف بين المجموعات. هذا ما دفع إلى استخدام معيارية التجزئة (Q) [ 13 ] كمقياس لتحسين تقسيم الرسم البياني المتوازن. يوضح المثال في الشكل 3 حالتين لنفس الرسم البياني، حيث تُستخدم معيارية التجزئة (Q) في (أ) ، بينما يُستخدم القطع النسبي في (ب) .

الشكل 3: يمكن تقسيم الرسم البياني الموزون G لتعظيم Q في (أ) أو لتقليل نسبة القطع في (ب). نلاحظ أن (أ) يمثل تقسيمًا أكثر توازنًا، مما يؤكد أهمية النمطية في مسائل تقسيم الرسوم البيانية.

التطبيقات

تصرف

تُستخدم دالة التوصيلية كدالة هدف أخرى لتقسيم الرسوم البيانية، وهي النسبة بين عدد الحواف المقطوعة وحجم أصغر جزء. ترتبط التوصيلية بالتدفقات الكهربائية والمسارات العشوائية. يضمن حد شيغر أن التنصيف الطيفي يُنتج تقسيمات ذات توصيلية شبه مثالية. تعتمد جودة هذا التقريب على ثاني أصغر قيمة ذاتية لمؤثر لابلاس λ² .

التطعيم

يمكن أن يكون تقسيم الرسم البياني مفيدًا لتحديد الحد الأدنى من مجموعة العقد أو الروابط التي يجب تحصينها من أجل وقف الأوبئة. [ 14 ]

طرق أخرى لتقسيم الرسم البياني

استُخدمت نماذج الدوران لتجميع البيانات متعددة المتغيرات، حيث تُترجم أوجه التشابه إلى قوى اقتران. [ 15 ] يمكن تفسير خصائص تكوين الدوران في الحالة الأرضية مباشرةً على أنها مجموعات. وبالتالي، يُقسّم الرسم البياني لتقليل دالة هاميلتون للرسم البياني المُقسّم. تُشتق دالة هاميلتون (H) من خلال تحديد مكافآت وعقوبات التقسيم التالية.

  • مكافأة الحواف الداخلية بين العقد من نفس المجموعة (نفس الدوران)
  • معاقبة الحواف المفقودة في نفس المجموعة
  • معاقبة الروابط القائمة بين المجموعات المختلفة
  • كافئ العلاقات غير المباشرة بين المجموعات المختلفة.

بالإضافة إلى ذلك، يتخذ التجميع الطيفي القائم على تحليل المكونات الرئيسية باستخدام النواة شكل إطار عمل آلة المتجهات الداعمة للمربعات الصغرى، وبالتالي يصبح من الممكن إسقاط مدخلات البيانات على فضاء ميزات مستحث بواسطة النواة يتميز بأقصى تباين، مما يعني فصلًا عاليًا بين المجتمعات المسقطة. [ 16 ]

تُعبّر بعض الطرق عن تقسيم الرسم البياني كمشكلة تحسين متعددة المعايير يمكن حلها باستخدام طرق محلية مُعبّر عنها في إطار نظرية الألعاب حيث تتخذ كل عقدة قرارًا بشأن التقسيم الذي تختاره. [ 17 ]

في حالة الرسوم البيانية الموزعة واسعة النطاق، قد لا تُجدي طرق التقسيم التقليدية نفعًا (مثل التقسيم الطيفي ، Metis [ 7 ] )، لأنها تتطلب الوصول الكامل إلى بيانات الرسم البياني لإجراء عمليات شاملة. في مثل هذه السيناريوهات واسعة النطاق، يُستخدم تقسيم الرسوم البيانية الموزعة لإجراء التقسيم من خلال عمليات محلية غير متزامنة فقط.

أدوات البرمجيات

تُنفذ مكتبة scikit-learn التجميع الطيفي مع تحديد التقسيم من المتجهات الذاتية لمصفوفة لابلاس للرسم البياني الأصلي المحسوبة بواسطة ARPACK ، أو بواسطة محلل LOBPCG مع التكييف المسبق متعدد الشبكات . [ 9 ]

METIS [ 7 ] هي عائلة من خوارزميات تقسيم الرسوم البيانية من تطوير كاريبس وكومار. من بين هذه العائلة، تهدف kMetis إلى زيادة سرعة التقسيم، بينما تُطبق hMetis [ 8 ] على الرسوم البيانية الفائقة وتهدف إلى تحسين جودة التقسيم، أما ParMetis [ 7 ] فهي تطبيق متوازٍ لخوارزمية تقسيم الرسوم البيانية Metis.

KaHyPar [ 18 ] [ 19 ] [ 20 ] هو إطار عمل لتقسيم الرسوم البيانية الفائقة متعددة المستويات، يوفر خوارزميات تقسيم مباشرة تعتمد على k-way وخوارزميات تقسيم ثنائية متكررة. يجسد هذا الإطار نهج التقسيم متعدد المستويات في أقصى صوره، حيث يزيل رأسًا واحدًا فقط في كل مستوى من مستويات التسلسل الهرمي. وباستخدام هذا النهج الدقيق للغاية ذي n مستوى، بالإضافة إلى خوارزميات بحث محلية قوية، فإنه يحسب حلولًا عالية الجودة.

سكوتش [ 21 ] هو إطار عمل لتقسيم الرسوم البيانية من ابتكار بيليغريني. يستخدم التقسيم الثنائي متعدد المستويات المتكرر ويتضمن تقنيات التقسيم المتسلسل والمتوازي.

يُعدّ برنامج Jostle [ 22 ] برنامجًا لحلّ مسائل تقسيم الرسوم البيانية بشكل متسلسل ومتوازي، وقد طوّره كريس والشاو. ويُعرف الإصدار التجاري من هذا البرنامج باسم NetWorks.

يقوم Party [ 23 ] بتنفيذ إطار عمل Bubble / shape-optimized وخوارزمية Helpful Sets.

تقوم حزم البرامج DibaP [ 24 ] ومتغيرها المتوازي MPI PDibaP [ 25 ] بواسطة Meyerhenke بتنفيذ إطار عمل Bubble باستخدام الانتشار؛ كما تستخدم DibaP تقنيات AMG للتخشين وحل الأنظمة الخطية الناشئة في النهج الانتشارى.

أصدر ساندرز وشولز حزمة تقسيم الرسوم البيانية KaHIP [ 26 ] (تقسيم كارلسروه عالي الجودة) التي تنفذ على سبيل المثال الأساليب القائمة على التدفق، وعمليات البحث المحلية الأكثر تحديدًا، والعديد من الطرق الاستدلالية المتوازية والمتسلسلة.

تركز أدوات Parkway [ 27 ] بواسطة Trifunovic و Knottenbelt وكذلك Zoltan [ 28 ] بواسطة Devine et al. على تقسيم الرسم البياني الفائق.

مراجع

  1. 1 2 3 4 5 أندرييف، كونستانتين؛ راكه، هارالد (2004). "تقسيم الرسوم البيانية المتوازن". وقائع الندوة السنوية السادسة عشرة لجمعية ACM حول التوازي في الخوارزميات والهياكل . برشلونة، إسبانيا. ص 120-124 . CiteSeerX 10.1.1.417.8592 . doi : 10.1145/1007912.1007931 . ISBN   978-1-58113-840-5.{{cite book}}: CS1 maint: موقع الناشر مفقود ( رابط )
  2. ↑ بولوك، أيدين؛ مايرهينكه، هينينغ؛ سافرو، إيليا؛ ساندرز، بيتر ؛ شولز، كريستيان (2013). "التطورات الحديثة في تقسيم الرسوم البيانية". arXiv : 1311.3144 [ cs.DS ].
  3. ↑ فيلدمان، أندرياس إميل؛ فوشيني، لوكا (2012). "التقسيمات المتوازنة للأشجار وتطبيقاتها". وقائع الندوة الدولية التاسعة والعشرين حول الجوانب النظرية لعلوم الحاسوب : 100-111 .
  4. 1 2 فيلدمان، أندرياس إميل (2012). "التقسيم المتوازن السريع صعب، حتى على الشبكات والأشجار". وقائع الندوة الدولية السابعة والثلاثين حول الأسس الرياضية لعلوم الحاسوب . arXiv : 1111.6745 . Bibcode : 2011arXiv1111.6745F .
  5. ↑ غاري، مايكل ر.؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان وشركاه. ISBN 978-0-7167-1044-8.
  6. ↑ هندريكسون، ب.؛ ليلاند، ر. (1995). خوارزمية متعددة المستويات لتقسيم الرسوم البيانية . وقائع مؤتمر ACM/IEEE للحوسبة الفائقة لعام 1995. ACM. ص 28. 
  7. 1 2 3 4 كاريبس، ج.؛ كومار، ف. (1999). "مخطط متعدد المستويات سريع وعالي الجودة لتقسيم الرسوم البيانية غير المنتظمة". مجلة SIAM للحوسبة العلمية . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi : 10.1137/S1064827595287997 . S2CID 3628209 .  
  8. 1 2 كاريبس، ج.؛ أغاروال، ر.؛ كومار، ف.؛ شيخار، س. (1997). تقسيم المخططات الفائقة متعددة المستويات: تطبيق في مجال VLSI . وقائع المؤتمر السنوي الرابع والثلاثين لأتمتة التصميم. ص 526-529 . 
  9. 1 2 كنيازيف، أندرو ف. (2006). تقسيم الرسم البياني الطيفي متعدد المقاييس وتجزئة الصور . ورشة عمل حول الخوارزميات لمجموعات البيانات الضخمة الحديثة، جامعة ستانفورد وياهو! للأبحاث.
  10. ↑ ج. ديميل،مؤرشف بتاريخ 6 مايو 2018 في أرشيف الإنترنت (Wayback Machine )، CS267: ملاحظات للمحاضرة 23، 9 أبريل 1999، تقسيم الرسوم البيانية، الجزء 2
  11. ↑ كنيازيف، أندرو (2018). حول التقسيم الطيفي للرسوم البيانية الموقعة . ورشة عمل SIAM الثامنة حول الحوسبة العلمية التوافقية، CSC 2018، بيرغن، النرويج، 6-8 يونيو. arXiv : 1701.01394 . doi : 10.1137/1.9781611975215.2 .
  12. ↑ ناوموف، م.؛ مون، ت. (2016). "تقسيم الرسم البياني الطيفي المتوازي" . تقرير فني من إنفيديا . nvr-2016-001. مؤرشف من الأصل بتاريخ 2016-05-05 . تم الاطلاع عليه بتاريخ 2016-04-20 .
  13. ↑ نيومان، إم إي جيه (2006). "النمطية وبنية المجتمع في الشبكات" . وقائع الأكاديمية الوطنية للعلوم . 103 ( 23): 8577-8696 . arXiv : physics/0602124 . Bibcode : 2006PNAS..103.8577N . doi : 10.1073/pnas.0601602103 . PMC 1482622. PMID 16723398 .  
  14. ↑ واي. تشين، جي. بول، إس. هافلين، إف. ليليروس، إتش إي ستانلي (2009). "إيجاد استراتيجية تحصين أفضل". مجلة Physical Review Letters ، المجلد 101 (5)، العدد 058701. doi : 10.1103/PhysRevLett.101.058701 . PMID 18764435 . {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  15. ↑ رايشاردت، يورغ؛ بورنهولت، ستيفان (يوليو 2006). "الميكانيكا الإحصائية للكشف عن المجتمعات". مجلة الفيزياء E. 74 ( 1) 016110. arXiv : cond-mat/0603718 . Bibcode : 2006PhRvE..74a6110R . doi : 10.1103 /PhysRevE.74.016110 . PMID 16907154. S2CID 792965 .  
  16. ↑ ألزات، كارلوس؛ سويكنز، يوهان أ.ك. (2010). "التجميع الطيفي متعدد الاتجاهات مع امتدادات خارج العينة من خلال تحليل المكونات الرئيسية الموزون". معاملات IEEE في تحليل الأنماط والذكاء الآلي . 32 (2): 335-347 . رمز Bibcode : 2010ITPAM..32..335A . doi : 10.1109/TPAMI.2008.292 . ISSN 0162-8828 . PMID 20075462. S2CID 200488 .   
  17. ↑ كورف، أ.؛ غريفين، س.؛ كيسيديس، ج. (2011) "لعبة تقسيم الرسوم البيانية للمحاكاة الموزعة للشبكات"، وقائع ورشة العمل الدولية لعام 2011 حول نمذجة وتحليل والتحكم في الشبكات المعقدة : 9-16
  18. ↑ شلاغ، س.؛ هين، ف.؛ هوير، ت.؛ مايرهينكه، هـ.؛ ساندرز، ب.؛ شولز، س. (30-12-2015). "تقسيم الرسم البياني الفائق K-way عبر التقسيم الثنائي المتكرر n-Level". وقائع ورشة العمل الثامنة عشرة حول هندسة الخوارزميات والتجارب (ALENEX) لعام 2016. جمعية الرياضيات الصناعية والتطبيقية. ص 53-67 . arXiv : 1511.03137 . doi : 10.1137/1.9781611974317.5 . ISBN  978-1-61197-431-7. S2CID 1674598 . 
  19. ↑ أخيرمتسيف، ي.؛ هوير، ت.؛ ساندرز، ب.؛ شلاغ، س. (2017-01-01). "هندسة خوارزمية تقسيم الرسم البياني الفائق k-way المباشرة". وقائع ورشة العمل التاسعة عشرة حول هندسة الخوارزميات والتجارب (ALENEX) لعام 2017. جمعية الرياضيات الصناعية والتطبيقية. ص 28-42 . doi : 10.1137/1.9781611974768.3 . ISBN  978-1-61197-476-8.
  20. ↑ هوير، توبياس؛ شلاغ، سيباستيان (2017). "تحسين مخططات التخشين لتقسيم الرسوم البيانية الفائقة من خلال استغلال بنية المجتمع". في: إيليوبولوس، كوستاس س.؛ بيسيس، سولون ب.؛ بوغليسي، سيمون ج.؛ رامان، راجيف (محررون). الندوة الدولية السادسة عشرة حول الخوارزميات التجريبية (SEA 2017) . وقائع لايبنيز الدولية في المعلوماتية (LIPIcs). المجلد 75. داغشتول، ألمانيا: قصر داغشتول - مركز لايبنيز للمعلوماتية. الصفحات 21:1-21:19. doi : 10.4230/LIPIcs.SEA.2017.21 . ISBN   978-3-95977-036-1.
  21. ↑ شيڤالييه، سي.؛ بيليغريني، إف. (2008). "PT-Scotch: أداة لترتيب الرسوم البيانية المتوازية بكفاءة". الحوسبة المتوازية . 34 (6): 318-331 . arXiv : 0907.1375 . doi : 10.1016/j.parco.2007.12.001 . S2CID 10433524 . 
  22. ↑ والشاو، سي.؛ كروس، إم. (2000). "تقسيم الشبكة: خوارزمية موازنة وتحسين متعددة المستويات". مجلة SIAM للحوسبة العلمية . 22 (1): 63-80 . Bibcode : 2000SJSC...22...63W . CiteSeerX 10.1.1.19.1836 . doi : 10.1137/s1064827598337373 . 
  23. ↑ ديكمان، ر.؛ بريس، ر.؛ شليمباخ، ف.؛ والشاو، س. (2000). "تقسيم الشبكة الأمثل للشكل وموازنة الأحمال لطريقة العناصر المحدودة التكيفية المتوازية". الحوسبة المتوازية . 26 (12): 1555-1581 . CiteSeerX 10.1.1.46.5687 . doi : 10.1016/s0167-8191(00)00043-0 . 
  24. ↑ مايرهينك، هـ.؛ مونين، ب.؛ ساوروالد، ت. (2008). "خوارزمية جديدة متعددة المستويات قائمة على الانتشار لحساب تقسيمات الرسوم البيانية". مجلة الحوسبة المتوازية والحوسبة الموزعة . 69 (9): 750-761 . CiteSeerX 10.1.1.702.7275 . doi : 10.1016/j.jpdc.2009.04.005 . S2CID 9755877 .  
  25. ↑ مايرهينك، هـ. (2013). موازنة الأحمال الأمثل للشكل في عمليات المحاكاة العددية التكيفية المتوازية باستخدام MPI . التحدي العاشر لتنفيذ DIMACS حول تقسيم الرسوم البيانية وتجميعها. الصفحات 67-82 . 
  26. ↑ ساندرز، ب .؛ شولز، س. (2011). هندسة خوارزميات تقسيم الرسوم البيانية متعددة المستويات . وقائع الندوة الأوروبية التاسعة عشرة حول الخوارزميات (ESA). المجلد 6942. الصفحات 469-480 .  
  27. ↑ تريفونوفيتش، أ.؛ نوتنبلت، دبليو جيه (2008). "خوارزميات متعددة المستويات متوازية لتقسيم الرسوم البيانية الفائقة". مجلة الحوسبة المتوازية والموزعة . 68 (5): 563-581 . CiteSeerX 10.1.1.641.7796 . doi : 10.1016/j.jpdc.2007.11.002 . 
  28. ↑ ديفاين، ك.؛ بومان، إ.؛ هيفي، ر.؛ بيسلينغ، ر.؛ كاتاليوريك، أ. (2006). تقسيم المخططات الفائقة المتوازية للحوسبة العلمية . وقائع المؤتمر الدولي العشرين حول المعالجة المتوازية والموزعة. ص 124. 

للمزيد من القراءة

  • بيشو، تشارلز إدموند؛ سياري، باتريك (2011). تقسيم الرسوم البيانية: التحسين والتطبيقات . ISTE – وايلي. ISBN 978-1-84821-233-6.