Graph-Theoretic Analysis of de Bruijn Graphs: Fault Resilience and Fragility
- سال انتشار: 1402
- محل انتشار: فصلنامه نوآوری های علوم و مهندسی کامپیوتر، دوره: 1، شماره: 2
- کد COI اختصاصی: JR_JICSE-1-2_005
- زبان مقاله: انگلیسی
- تعداد مشاهده: 9
نویسندگان
Faculty of Computer Science and Engineering, Shahid Beheshti University, Tehran, Iran
Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
Department of Computer Engineering, University of Torbat Heydarieh, Razavi Khorasan Province, IRAN
چکیده
The de Bruijn graph, initially proposed as a topological architecture for interconnection networks, offers unique attributes. These graphs are regular, Eulerian, and Hamiltonian, boasting a small diameter close to optimal connectivity. Their low average distance, small diameter, and high connectivity contribute to remarkable fault tolerance against both node and edge failures. Comprehensively, these graphs serve as pivotal components in word-representing networks, finding applications in various scientific and engineering domains, particularly in genome assembly. They play a significant role in bioinformatics, information theory, coding, communication networks, and multiprocessors. Additionally, de Bruijn graphs are utilized in peer-to-peer (P۲P) networks and distributed hash tables (DHT), demonstrating their versatility. Moreover, de Bruijn graphs can serve as a robust infrastructure for modeling online/offline user behavior. In this article, we delve into the different types of de Bruijn graphs and their unique properties from a graph theory perspective. Our focus is on evaluating the reliability of these graphs concerning resilience, fragility, and vulnerability to random failures and targeted attacks on both nodes and edges.کلیدواژه ها
Graph theory, Interconnection Networks, de Bruijn Graph, Fault-Tolerance, Graph Resilience, Network Fragilityاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.