The minimum spanning subgraph problem with given cyclomatic number

zbMATH Open1330.90097MaRDI QIDQ3466909FDOQ3466909

Authors: Qin Wang, Jinjiang Yuan 

Publication date: 25 January 2016

Full work available at URL: http://www.yokohamapublishers.jp/online2/oppjo/vol11/p583.html

Recommendations

• Algorithms for shortest paths and \(d\)-cycle problems
• Minimum-weight subgraphs with unicyclic components and a lower-bounded girth
• Minimum 2-edge connected spanning subgraph of certain graphs
• On the Structure of Minimum-Weight k-Connected Spanning Networks
• Minimum face-spanning subgraphs of plane graphs

zbMATH Keywords

polynomial time algorithmcyclomatic numberstrongly NP-hardreverse problemminimum spanning subgraph

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (1)

• The minimum spanning strong subdigraph problem is fixed parameter tractable

This page was built for publication: The minimum spanning subgraph problem with given cyclomatic number

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