Given　an　integer　L∈Z+　and　an　undirected　graph　with　a　weight　and　a　length　associated　with　every　edge,　the　constrained　minimum　spanning　tree　(CMST)　problem　is　to　compute　a　minimum　weight　spanning　tree　with　total　length　bounded　by　L.　The　problem　was　shown　weakly　NP-hard　in　[1],　admitting　a　PTAS　with　a　runtime　O(nO(1ϵ)(mlog2n+nlog3n))　due　to　Ravi　and　Goemans　[13].　In　the　paper,　we　present　an　exact　algorithm　for　CMST,　based　on　our　developed　bicameral　edge　replacement　which　improves　a　feasible　solution　of　CMST　towards　an　optimal　solution.　By　applying　the　classical　rounding　and　scaling　technique　to　the　exact　algorithm,　we　can　obtain　a　fully　polynomial-time　approximation　scheme　(FPTAS),　i.e.　an　approximation　algorithm　with　a　ratio　(1　+　ϵ)　and　a　runtime　O(mn51ϵ2),　where　ϵ>0　is　any　fixed　real　number.　©　Springer　International　Publishing　AG　2017.