Hakan KUTUCU

Bases of polymatroids and problems on graphs

In the paper, we present new theorems to show that a Hamiltonian path and circuit on an undirected graph can be formulated in terms of bases of polymatroids or extended polymatroids associated with submodular functions defined on subsets of the node-set of a given graph. In this way, we give a new formulation of the well-known traveling salesman problem including constraints in these terms. The main result in the paper states that using a special base of the polymatroid, a Hamiltonian path on an undirected graph can be solved effectively. Since the determination of a Hamiltonian circuit can be reduced to finding a Hamiltonian path between some node and its adjacent nodes, an efficient Hamiltonian path algorithm will lead to solving the Hamiltonian circuit problem. Finding some special base is the main problem in solving these N P -hard problems

PDF

___

[1] Iwata S. Submodular function minimization. Mathematical Programming: Series A and B 2008; 112 (1): 45-64. doi: 10.1007/s10107-006-0084-2
[2] Fujishige S. Submodular Functions and Optimization. Annals of Discrete Mathematics, Vol. 58. 2nd ed. New York, NY, USA: Elsevier, 2005.
[3] Swamy MNS, Txulasiraman K. Graphs, Networks, and Algorithms. New York, NY, USA: A Wiley Interscience Publication, John Wiley & Sons, 1981.
[4] Sharifov FA. Perfectly matchable subgraph problem on a bipartite graph. RAIRO-Operations Research 2010; 44 (1): 27-42. doi:10.1051/ro/2010004
[5] Sharifov FA. Perfect matching and polymatroids. Cybernetics and System analysis 2017; 53 (5): 753-758. doi: 10.1007/s10559-017-9977-8
[6] Akhmedov A, Winter M. Chordal and timbral morphologies using Hamiltonian cycles. Journal of Mathematics and Music 2014; 8(1): 1-24. doi: 10.1080/17459737.2014.893033
[7] Bollobas B, Fenner TI, Frieze AM. An algorithm for finding Hamilton paths and cycles in random graphs. Combi- natorica 1987; 7 (4): 327-341. doi: 10.1007/BF02579321
[8] Ore O. Note on Hamilton circuits. American Mathematical Monthly, Mathematical Association of America 1960; 67 (1): 55-55. doi: 10.2307/2308928
[9] Dirac GA. Some theorems on abstract graphs. Proceedings of the London Mathematical Society 1952; 3 (1): 69–81. doi: 10.1112/plms/s3-2.1.69
[10] Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. The traveling salesman problem. Chichester, UK: John Wiley, 1985
11] Sharifov F, Kutucu H. Network design problem with cut constraints. In: Goldengorin B (editors). Optimization Problems in Graph Theory, Springer Optimization and Its Applications. Cham, Switzerland: Springer, 2018, pp. 265-292.
[12] Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (editors). Complexity of Computer Computations. The IBM Research Symposia Series. Boston, MA, USA: Springer, 1972.
[13] Wang DL, Kleitman DJ. A note on n -edge connectivity. SIAM Journal on Applied Mathematics 1974; 26 (2): 313-314. doi: 10.1137/0126029