✦ LIBER ✦

On the complexity of finding multi-constrained spanning trees

✍ Scribed by P.M. Camerini; G. Galbiati; F. Maffioli

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 602 KB
Volume: 5
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(83)90014-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Finding the Graph with the Maximum Numbe

Finding the Graph with the Maximum Number of Spanning Trees

✍ George Moustakides; Samuel D. Bedrosian 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 328 KB

The problem is to determine the linear graph that has the maximum number of spanning trees, where only the number of nodes N and the number of branches B are prescribed. We deal with connected graphs G(N, B) obtained by deleting D branches from a complete graph KN. Our solution is for D less than or

On the spanning trees of weighted graphs

✍ Ernst W. Mayr; C. Greg Plaxton 📂 Article 📅 1992 🏛 Springer-Verlag 🌐 English ⚖ 874 KB

The NP-completeness of finding A-trails

The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs

✍ Lars Døvling Andersen; Herbert Fleischner 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 821 KB

Bounds on the number of disjoint spannin

Bounds on the number of disjoint spanning trees

✍ Sukhamay Kundu 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 260 KB

On the complexity of algorithms on recur

On the complexity of algorithms on recursive trees

✍ Jerzy Szymański 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 476 KB

On graphs with the maximum number of spa

On graphs with the maximum number of spanning trees

✍ Alexander K. Kelmans 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 814 KB

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta