Complexity of finding a join of maximum weight

DOI10.1016/S0166-218X(00)00355-3zbMath0996.05109OpenAlexW2085666698MaRDI QIDQ5954077

A. A. Ageev

Publication date: 30 January 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00355-3

zbMATH Keywords

joinpolynomial-time algorithmNP-hard problemseries-parallel graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Approximating max-min weighted \(T\)-joins

Cites Work

• Unnamed Item
• Undirected distances and the postman-structure of graphs
• Conservative weightings and ear-decompositions of graphs
• Topology of series-parallel networks
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• The Recognition of Series Parallel Digraphs
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs