Academic Journal
A tight relation between series--parallel graphs and bipartite distance hereditary graphs
| العنوان: | A tight relation between series--parallel graphs and bipartite distance hereditary graphs |
|---|---|
| المؤلفون: | Apollonio, Nicola, Caramia, Massimiliano, Franciosa, Paolo Giulio, Mascari, Jean-François |
| المساهمون: | Apollonio, N, Caramia, M, Franciosa, Pg, Mascari, J |
| سنة النشر: | 2022 |
| المجموعة: | Universitá degli Studi di Roma "Tor Vergata": ART - Archivio Istituzionale della Ricerca |
| مصطلحات موضوعية: | Seies-parallel graphs, bipartite distance hereditary graphs, binary matroids, Settore MAT/09 - RICERCA OPERATIVA |
| الوصف: | Bandelt and Mulder’s structural characterization of bipartite distance hereditary graphs asserts that such graphs can be built inductively starting from a single vertex and by re17 peatedly adding either pendant vertices or twins (i.e., vertices with the same neighborhood as an existing one). Dirac and Duffin’s structural characterization of 2–connected series–parallel graphs asserts that such graphs can be built inductively starting from a single edge by adding either edges in series or in parallel. In this paper we give an elementary proof that the two constructions are the same construction when bipartite graphs are viewed as the fundamental graphs of a graphic matroid. We then apply the result to re-prove known results concerning bipartite distance hereditary graphs and series–parallel graphs and to provide a new class of polynomially-solvable instances for the integer multi-commodity flow of maximum value |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| Relation: | volume:5; issue:1; firstpage:1; lastpage:17; numberofpages:17; journal:THE ART OF DISCRETE AND APPLIED MATHEMATICS; http://hdl.handle.net/2108/283891; info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85128657992 |
| DOI: | 10.26493/2590-9770.1396.3c7 |
| الاتاحة: | http://hdl.handle.net/2108/283891 https://doi.org/10.26493/2590-9770.1396.3c7 |
| Rights: | info:eu-repo/semantics/openAccess |
| رقم الانضمام: | edsbas.3EE4DEF7 |
| قاعدة البيانات: | BASE |
| DOI: | 10.26493/2590-9770.1396.3c7 |
|---|