The minimum spanning subgraph problem with given cyclomatic number

MaRDI QIDQ3466909zbMATH OpenFDO

Authors Qin Wang, Jinjiang Yuan

Publication date 25 January 2016

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

zbMATH Keywords

polynomial time algorithmcyclomatic numberstrongly NP-hardreverse problemminimum spanning subgraph

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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

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)