Nested Graphs

Mark Korenblit; Vadim E. Levit

doi:10.1016/j.endm.2006.06.016

Nested Graphs

Mark Korenblit
, Vadim E. Levit

פרסום מחקרי: פרסום בכתב עת › מאמר › ביקורת עמיתים

1 ציטוט ‏(Scopus)

תקציר

We define a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. It is proved that every nested graph is series-parallel as well. We show that an st-dag of order n has exactly n - 1 mincuts if and only if it is nested.

שפה מקורית	אנגלית
עמודים (מ-עד)	93-99
מספר עמודים	7
כתב עת	Electronic Notes in Discrete Mathematics
כרך	24
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.1016/j.endm.2006.06.016
סטטוס פרסום	פורסם - 15 יולי 2006
פורסם באופן חיצוני	כן

גישה למסמך

10.1016/j.endm.2006.06.016

קבצים וקישורים אחרים

Link to publication in Scopus

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

@article{199778c06add47c1974b90ae4336e10d,

title = "Nested Graphs",

abstract = "We define a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. It is proved that every nested graph is series-parallel as well. We show that an st-dag of order n has exactly n - 1 mincuts if and only if it is nested.",

keywords = "Mincut, directed acyclic graph, series-parallel graph",

author = "Mark Korenblit and Levit, \{Vadim E.\}",

year = "2006",

month = jul,

day = "15",

doi = "10.1016/j.endm.2006.06.016",

language = "אנגלית",

volume = "24",

pages = "93--99",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Nested Graphs

AU - Korenblit, Mark

AU - Levit, Vadim E.

PY - 2006/7/15

Y1 - 2006/7/15

N2 - We define a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. It is proved that every nested graph is series-parallel as well. We show that an st-dag of order n has exactly n - 1 mincuts if and only if it is nested.

AB - We define a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. It is proved that every nested graph is series-parallel as well. We show that an st-dag of order n has exactly n - 1 mincuts if and only if it is nested.

KW - Mincut

KW - directed acyclic graph

KW - series-parallel graph

UR - https://www.scopus.com/pages/publications/33745867972

U2 - 10.1016/j.endm.2006.06.016

DO - 10.1016/j.endm.2006.06.016

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:33745867972

SN - 1571-0653

VL - 24

SP - 93

EP - 99

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Nested Graphs

תקציר

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

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