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

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

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


عنوان مقاله:سریع تر نمایی زمان الگوریتم در نمودار های متوسط ​​درجه محدود
ناشر: [ 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: 52.55.186.225

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

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

 

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

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

خلاصه مقاله، نویسندگان و کلمات کلیدی

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



[ ]

فهرست مقالات مرتبط و مشابه

  1. Cygan, Marek, Pilipczuk, Marcin (2013) 'Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree', Automata, Languages, and Programming, Springer Nature, pp:364-375
  2. Pilipczuk, Marcin (2015) 'Exact Algorithms on Graphs of Bounded Average Degree', Encyclopedia of Algorithms, Springer US, pp:1-4
  3. (2012) 'Algorithms for bounded degree graphs', Large Networks and Graph Limits, American Mathematical Society, pp:397-412
  4. Chen, Jianer (1993) 'A linear time algorithm for isomorphism of graphs of bounded average genus', Graph-Theoretic Concepts in Computer Science, Springer Nature, pp:103-113
  5. (2017) 'exponential-bounded (-time)Exponential-bounded (-time) algorithm', Encyclopedia of Operations Research and Management Science, Springer Nature, pp:275-275
  6. Lelarge, Marc, Zhou, Hang (2014) 'Sublinear-time algorithms for monomer–dimer systems on bounded degree graphs', Theoretical Computer Science, Elsevier BV, pp:68-78
  7. Thilikos, Dimitrios M., Serna, Maria J., Bodlaender, Hans L. (2001) 'A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth', Algorithms — ESA 2001, Springer Nature, pp:380-390
  8. Capocelli, Renato M., Gargano, Luisa, Vaccaro, Ugo (1990) 'Time bounds for broadcasting in bounded degree graphs', Graph-Theoretic Concepts in Computer Science, Springer Berlin Heidelberg, pp:19-33
  9. Chang, Maw-Shang, Chen, Li-Hsuan, Hung, Ling-Ju, Liu, Yi-Zhi, Rossmanith, Peter, Sikdar, Somnath (2018) 'Moderately exponential time algorithms for the maximum bounded-degree-1 set problem', Discrete Applied Mathematics, Elsevier BV, pp:-
  10. Przybyło, Jakub, Raspaud, André, Woźniak, Mariusz (2017) 'On weight choosabilities of graphs with bounded maximum average degree', Discrete Applied Mathematics, Elsevier BV, pp:663-672

 

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




 

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