ميتيس

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

METIS هي حزمة برمجية لتقسيم الرسوم البيانية ، وتنفذ خوارزميات متعددة المستويات متنوعة . [ 1 ] [ 2 ] يتكون نهج METIS متعدد المستويات من ثلاث مراحل، ويأتي مع عدة خوارزميات لكل مرحلة:

  1. قم بتخشين الرسم البياني عن طريق إنشاء سلسلة من الرسوم البيانية G 0 ، G 1 ، ... ، G N ، حيث G 0 هو الرسم البياني الأصلي ولكل 0 ≤ i < j ≤ N ، يكون عدد الرؤوس في G i أكبر من عدد الرؤوس في G j .
  2. احسب تجزئة G N
  3. قم بإسقاط التقسيم مرة أخرى من خلال التسلسل بالترتيب G N ، ... ، G 0 ، مع تحسينه بالنسبة لكل رسم بياني.

التقسيم النهائي الذي تم حسابه خلال المرحلة الثالثة (التقسيم المحسن المسقط على G 0 ) هو تقسيم للرسم البياني الأصلي.

بحسب مؤلفي ميتيس، كاريبس وكومار، فإن "ميتيس هي الكلمة اليونانية التي تعني الحكمة. كانت ميتيس إحدى التيتانيات في الأساطير اليونانية. كانت زوجة زيوس وأم أثينا. كانت مسؤولة عن كل الحكمة والمعرفة". [ 3 ]

مراجع

  1. ↑ جورج كاريبس وفيبين كومار (1995). METIS - نظام تقسيم الرسوم البيانية غير المهيكلة وترتيب المصفوفات المتفرقة، الإصدار 2.0 (تقرير فني).
  2. ↑ كاريبس، ج. وكومار، ف. (1999). "مخطط متعدد المستويات سريع وعالي الجودة لتقسيم الرسوم البيانية غير المنتظمة". مجلة SIAM للحوسبة العلمية . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi : 10.1137/S1064827595287997 . S2CID 3628209 .  
  3. ↑ كاريبس، جورج؛ كومار، فيبين (1997). ميتيس: حزمة برمجية لتقسيم الرسوم البيانية غير المهيكلة، وتقسيم الشبكات، وحساب ترتيبات تقليل التعبئة للمصفوفات المتفرقة (تقرير). hdl : 11299/215346 .