سایپرز، باشگاه دانش - ارائه دهنده مقالات ژورنالهای خارجی

اطلاعات و مشخصات مقاله

explorer iconلينك‌ها

[ بازگشت | جستجو | فهرست کلمات کلیدی | فهرست موضوعات | فهرست نویسندگان | فهرست ناشران | فهرست ژورنالها ]

info iconاطلاعات مقاله

[ 120 بار مشاهده چكيده]

عنوان مقاله:سریع تر نمایی زمان الگوریتم در نمودار های متوسط ​​درجه محدود
ناشر: [ Elsevier BV ]
ژورنال
دوره (شماره): (0)
سال انتشار:August 2015
شماره صفحات: 758575-85
نشانگر دیجیتالی شیء:[ 10.1016/j.ic.2014.12.007 ]
شما اینجا هستید:
  1. Scipers, the Knowledge ClubScipers »
  2. Elsevier BV »
  3. Information And Computation »
  4. Faster exponential-time algorithms in graphs of bounded average degree

دسترسی بین المللی

اگر شما در داخل کشور (ایران) هستید و این صفحه را مشاهده می کنید، نشان می دهد که IP شما به هر دلیلی در لیست IP های ایران ثبت نشده است. برای رفع این مشکل کافی است IP خود را که در پایین این پیام درج شده از طریق آدرس ایمیل support@scipers.com به ما اطلاع دهید. پس از دریافت درخواست، کارشناسان فنی موضوع را بررسی می نمایند و در صورتی که محل اتصال شما از کشور ایران بوده باشد، به لیست استفاده کنندگان مجاز افزوده می شوید.
IP: 34.224.102.60

اطلاعات استنادی

اطلاعات استنادی این مقاله را به نرم افزارهای مدیریت اطلاعات علمی و استنادی ارسال نمایید و در تحقیقات خود از آن استفاده نمایید.

 

به اشتراک گذاری

این صفحه را با استفاده از انواع شبکه های اجتماعی با دوستان خود به اشتراک بگذارید.

report iconنمايش خلاصه مقاله

Faster Exponential-time Algorithms In Graphs Of Bounded Average Degree


مقاله: سریع تر نمایی زمان الگوریتم در نمودار های متوسط ​​درجه محدود

نويسند‌گان:


خلاصه مقاله:


We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree. First, we obtain a simple algorithm that computes a permanent of an n×n matrix over an arbitrary commutative ring with at most dn non-zero entries using O⋆(2(1−1/(3.55d))n) time and ring operations,1 improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012].Second, we present a simple algorithm for counting perfect matchings in an n-vertex graph in O⋆(2n/2) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Björklund [SODA 2012], but relies on inclusion–exclusion principle instead of algebraic transformations.Third, we show a combinatorial lemma that bounds the number of “Hamiltonian-like” structures in a graph of bounded average degree. Using this result, we show that1.a minimum weight Hamiltonian cycle in an n-vertex graph with average degree bounded by d can be found in O⋆(2(1−εd)n) time and exponential space for a constant εd depending only on d;2.the number of perfect matchings in an n-vertex graph with average degree bounded by d can be computed in O⋆(2(1−εd′)n/2) time and exponential space, for a constant εd′ depending only on d. The algorithm for minimum weight Hamiltonian cycle generalizes the recent results of Björklund et al. [TALG 2012] on graphs of bounded degree.


 


كلمات كليدي:

Bounded average degree , Counting perfect matchings , Minimum weight Hamiltonian cycle, Bounded average degree, Counting perfect matchings, Minimum weight Hamiltonian cycle, Moderately-exponential algorithms
Bounded average degree , Counting perfect matchings , Minimum weight Hamiltonian cycle , محدود درجه متوسط ​​| شمارش matchings کامل, حداقل چرخه هامیلتونی وزن, Minimum weight Hamiltonian cycle, الگوریتم نسبتا نمایی


موضوعات:

Theoretical Computer Science, Computational Theory and Mathematics, Information Systems, Computer Science Applications



[ ]

 

فهرست مراجع و منابع




 

برگشت به بالا
رونمایی از اولین و تنها ربات تلگرامی جستجوی مقالات ژورنالی
×