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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2003
פורסם באופן חיצוניכן

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך2731
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On algebraic expressions of series-parallel and Fibonacci graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי