ترجمه مقاله الگوریتم هایی برای مسیرهای طولانی در گراف

Algorithms for long paths in graphs

ترجمه مقاله الگوریتم هایی برای مسیرهای طولانی در گراف

دسته : فناوری اطلاعات

---

چکیده

در این مقاله، ما یک الگوریتم چندجمله  از مرتبه ی زمانی را ارائه میدهیم، که به وسیله ی آن، یک مسیر طولانی را در هر گراف با n راس و m یال پیدا کنیم. طول این مسیر، محدود به پارامترهای تعریف شده بر روی شرط مجاورت میباشد. مثالی نیز ارائه شده است تا نشان دهد که این مجموعه، نسبت به چندین نتیجه ی کلاسیکی بهتر عمل میکند.

فهرست مطالب

1-مقدمه و نمادها

2-اثبات قضیه ی اصلی

3-مراجع

Abstract

 

We obtain a polynomial algorithm in O(nm) time to find a long path in any graph with n vertices and m edges. The length of the path is bounded by a parameter defined on neighborhood condition of any three independent vertices of the path. An example is given to show that this bound is better than several classic results

Contents

1. Proof of the main theorem
2. References
3. Introduction and notation