أشجار الامتداد التي تقلل من تكلفة التفرع

تهدف مشكلة شجرة الامتداد بأقل عدد من رؤوس التفرع إلى إيجاد شجرة امتداد T في رسم بياني محدد G بأدنى عدد من رؤوس التفرع، والتي تعرف بأنها رؤوس ذات درجة ثلاثة أو أكثر في T. تُعتبر هذه المشكلة من الصعوبة NP، وقد جذبت اهتمامًا كبيرًا بسبب أهميتها في تصميم الشبكات وتحسينها. تم إجراء أبحاث واسعة على الجوانب الخوارزمية والتركيبية لهذه المشكلة، مع دراسة حديثة تتناول قابليتها للمعالجة بالنسبة للمعلمات الثابتة. في هذه الورقة، نركز بشكل أساسي على عرض المعلمة. نوضح أن إيجاد شجرة امتداد بأقل عدد من رؤوس التفرع هو قابل للمعالجة بالنسبة للمعلمات الثابتة (FPT) عند النظر إليها بالنسبة لعرض المعاملات. بالإضافة إلى ذلك، في الحالات التي يكون فيها لكل رأس في الرسم البياني المدخل تكلفته المرتبطة لخدمته كرأس تفرع، نثبت أن مشكلة إيجاد شجرة امتداد بأقل تكلفة تفرع (أي تقليل مجموع تكاليف رؤوس التفرع) قابلة للمعالجة بالنسبة للمعلمات الثابتة فيما يتعلق بتنوع الجوار.