Studies on Graphs and Discrete Programming (eBook)

Front Cover 1
Studies on Graphs and Discrete Programming 4
Copyright Page 5
Contents 8
Foreword 6
Chapter 1. Integer and fractional matchings 10
Chapter 2. Packing problems 24
Chapter 3. Admissible transformations and their application to matching problems 32
Chapter 4. Polynomial algorithms for totally dual integral systems and extensions 48
Chapter 5. Minimal costreliability ratio spanning tree 62
Chapter 6. A graph theoretic analysis of bounds for the quadratic assignment problem 70
Chapter 7. An investigation of algorithms used in the restructuring of linear programming basis matrices prior to inversion 78
Chapter 8. On the number of nonnegative integer solutions of a system of linear diophantine equations 104
Chapter 9. The administration of standard length telephone cable reels 118
Chapter 10. Threshold numbers and threshold completions 134
Chapter 11. Constrained location and the Weber–Rawls problem 156
Chapter 12. A bounding technique for integer linear programming with binary variables 176
Chapter 13. School timetables 186
Chapter 14. How to color claw-free perfect graphs 198
Chapter 15. Properties of some extremal problems of permutation cycles 208
Chapter 16. Minimal test set for diagnosing a tree system 224
Chapter 17. Sufficient conditions for graphs to have threshold number 2 250
Chapter 18. Optimum synthesis of a network with non-simultaneous multicommodity flow requirements 278
Chapter 19. Maximizing submodular set functions: formulations and analysis of algorithms 288
Chapter 20. A solvable machine maintenance model with applications 312
Chapter 21. Convergence of decomposition algorithms for the traffic assignment problem 322
Chapter 22. A recursive method for solving assignment problems 328
Chapter 23. Asymptotical estimations for the number of cliques of uniform hypergraphs 354
Chapter 24. A suggested extension of special ordered sets to non-separable non-convex programming problems 368
Chapter 25. Parametric multicriteria integer programming 380
Chapter 26. Scheduling in sports 390