Skip to main content
SpringerLink
Log in

Constrained inverse min–max spanning tree problems under the weighted Hamming distance

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this paper, we consider the constrained inverse min–max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Camerini P.M. (1978). The min–max spanning tree problem and some extensions. Inform. Process. Lett. 7: 10–14

    Article  Google Scholar 

  2. Yang X.G. and Zhang J.Z. (2007). Some inverse min–max network problems under weighted l 1 and l ∞ norms with bound constraints on changes. J. Comb. Optim. 13: 123–135

    Article  Google Scholar 

  3. Liu, L.C., Yao, E.Y.: Inverse min–max spanning tree problem under the weighted sum-type Hamming distance. In: Theor Comput Sci (2007). doi:10.1016/j.tcs.2007.12.006

  4. Heuberger C. (2004). Inverse Optimization: A survey on problems, methods and results. J. Comb. Optim. 8: 329–361

    Article  Google Scholar 

  5. He Y., Zhang B. and Yao E. (2005). Wighted inverse minimum spanning tree problems under Hamming distance. J. Comb. Optim. 9: 91–100

    Article  Google Scholar 

  6. He Y., Zhang B. and Zhang J. (2006). Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance. J. Glob. Optim. 34(3): 467–474

    Article  Google Scholar 

  7. Duin C.W. and Volgenant A. (2006). Some inverse optimization problems under the Hamming distance. Eur. J. Oper. Res. 170: 887–899

    Article  Google Scholar 

  8. Zhang B., Zhang J. and He Y. (2005). The center location improvement problem under the Hamming distance. J. Comb. Optim. 9: 187–198

    Article  Google Scholar 

  9. Yang, X.G., Zhang, J.Z.: Some new results on inverse sorting problems. In: Lecture Notes in Computer Science, vol. 3595, pp. 985–992 (2005)

  10. Liu L.C. and Zhang J.Z. (2006). Inverse maximum flow problems under the weighted Hamming distance. J. Comb. Optim. 12: 395–408

    Article  Google Scholar 

  11. Liu L.C. and Yao E.Y. (2007). Weighted inverse minimum cut problem under the bottleneck-type Hamming distance. Asia-Pac. J. Oper. Res. 24(5): 1–12

    Google Scholar 

  12. Guan, X., Zhang, J.: Inverse Bottleneck Optimization Problems under Weighted Hamming Distance. In: Lecture Notes in Computer Science, vol. 4041, pp. 220–230 (2006)

  13. Schrijver A. (2003). Combinatorial Optimization, Polyhedra and Efficiency. Springer-Verlag, Berlin

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Zhejiang University, Hangzhou, China

    Longcheng Liu

  2. Department of Mathematics, China Jiliang University, Hangzhou, China

    Qin Wang

Authors
  1. Longcheng Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Longcheng Liu.

Additional information

This research is supported by the National Natural Science Foundation of China (Grant No. 10601051).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, L., Wang, Q. Constrained inverse min–max spanning tree problems under the weighted Hamming distance. J Glob Optim 43, 83–95 (2009). https://doi.org/10.1007/s10898-008-9294-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-008-9294-x

Keywords

Search

Navigation