An efficiently solvable case of the minimum weight equivalent subgraph problem

DOI10.1002/NET.3230150207MaRDI QIDQ3706869zbMATH OpenOpenAlexFDO

Authors Michael B. Richey, R. G. Parker, Ronald L. Rardin

Publication date 1985

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230150207

zbMATH Keywords

directed networkminimum weight equivalent subgraph problemseries-parallel graphsstrong connectivity structure

Mathematics Subject Classification ID

Graph theory (05C99) Programming involving graphs or networks (90C35)

Recommendations

• Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems
• Generalized steiner problem in series-parallel networks
• Approximating the Minimum Equivalent Digraph
• Approximating the minimum strongly connected subgraph via a matching lower bound
• The Equivalent Subgraph and Directed Cut Polyhedra on Series-Parallel Graphs

Cited in

(9)

• Minimum-maximal matching in series-parallel graphs
• Algorithms for recognition of regular properties and decomposition of recursive graph families
• Minimum perfect bipartite matchings and spanning trees under categorization
• The point-to-point connection problem - analysis and algorithms
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• The Equivalent Subgraph and Directed Cut Polyhedra on Series-Parallel Graphs
• Capacity-preserving subgraphs of directed flow networks
• Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms

This page was built for publication: An efficiently solvable case of the minimum weight equivalent subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3706869)