On algebraic expressions of series-parallel and Fibonacci graphs

Mark Korenblit, Vadim E. Levit

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرفصلمراجعة النظراء

24 اقتباسات (Scopus)

ملخص

The paper investigates relationship between algebraic expressions and graphs. Through out the paper we consider two kinds of digraphs: series-parallel graphs and Fibonacci graphs (which give a generic example of non-series-parallel graphs). Motivated by the fact that the most compact expressions of series-parallel graphs are read-once formulae, and, thus, of O(n) length, we propose an algorithm generating expressions of O(n2) length for Fibonacci graphs. A serious effort was made to prove that this algorithm yields expressions with a minimum number of terms. Using an interpretation of a shortest path algorithm as an algebraic expression, a symbolic approach to the shortest path problem is proposed.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
المحررونCristian S. Calude, Michael J. Dinneen, Vincent Vajnovszki
الصفحات215-224
عدد الصفحات10
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2003
منشور خارجيًانعم

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت2731
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

بصمة

أدرس بدقة موضوعات البحث “On algebraic expressions of series-parallel and Fibonacci graphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا