A note on the recognition of nested graphs

Mark Korenblit, Vadim E. Levit

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

We consider a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. This graph is of interest as an st-dag with a minimum possible number of mincuts.We present a linear-time algorithm for recognizing nested graphs.

שפה מקוריתאנגלית
כותר פרסום המארחGraph Theory, Computational Intelligence and Thought - Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday
עורכיםMarina Lipshteyn, Vadim E. Levit, Ross M. McConnell
עמודים36-40
מספר עמודים5
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2009

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

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

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A note on the recognition of nested graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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