𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the multicut problem in bounded tree-width graphs and digraphs

✍ Scribed by Cédric Bentz

Book ID
108112713
Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
232 KB
Volume
156
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the complexity of graph tree partitio
On the complexity of graph tree partition problems
✍ Roberto Cordone; Francesco Maffioli 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 270 KB

This paper concerns the optimal partition of a graph into p connected clusters of vertices, with various constraints on their topology and weight. We consider di erent objectives, depending on the cost of the trees spanning the clusters. This rich family of problems mainly applies to telecommunicati

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
✍ Luc Devroye; Carlos Zamora-Cura 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co