Novel Techniques to Speed Up the Computation of the Automorphism Group of a Graph
المؤلفون المشاركون
López-Presa, José Luis
Fernández Anta, Antonio
Chiroque, Luis F.
المصدر
Journal of Applied Mathematics
العدد
المجلد 2014، العدد 2014 (31 ديسمبر/كانون الأول 2014)، ص ص. 1-15، 15ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2014-07-24
دولة النشر
مصر
عدد الصفحات
15
التخصصات الرئيسية
الملخص EN
Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph.
Most GA algorithms explore a search tree using the individualization-refinement procedure.
Four novel techniques are proposed which increase the performance of any algorithm of this type by reducing the depth of the search tree and by effectively pruning it.
We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of an input graph.
Then, we describe how these techniques have been incorporated into the GA algorithm conauto, as conauto-2.03, with at most an additive polynomial increase in its asymptotic time complexity.
Using a benchmark of different graph families, we have evaluated the impact of these techniques on the size of the search tree, observing a significant reduction both when they are applied individually and when all of them are applied together.
This is also reflected in a reduction of the running time, which is substantial for some graph families.
Finally, we have compared the search tree size of conauto-2.03 against those of other popular GA algorithms, observing that, in most cases, conauto explores less nodes than these algorithms.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
López-Presa, José Luis& Chiroque, Luis F.& Fernández Anta, Antonio. 2014. Novel Techniques to Speed Up the Computation of the Automorphism Group of a Graph. Journal of Applied Mathematics،Vol. 2014, no. 2014, pp.1-15.
https://search.emarefa.net/detail/BIM-509394
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
López-Presa, José Luis…[et al.]. Novel Techniques to Speed Up the Computation of the Automorphism Group of a Graph. Journal of Applied Mathematics No. 2014 (2014), pp.1-15.
https://search.emarefa.net/detail/BIM-509394
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
López-Presa, José Luis& Chiroque, Luis F.& Fernández Anta, Antonio. Novel Techniques to Speed Up the Computation of the Automorphism Group of a Graph. Journal of Applied Mathematics. 2014. Vol. 2014, no. 2014, pp.1-15.
https://search.emarefa.net/detail/BIM-509394
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-509394
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر