Bases of polymatroids and problems on graphs

Authors

HAKAN KUTUCU

DOI

10.3906/elk-1909-102

Abstract

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 NP -hard problems.

Keywords

Submodular function, bases of polymatroid, hamiltonian path and circuit, traveling salesman problem

First Page

1905

Last Page

1915

Recommended Citation

KUTUCU, HAKAN (2020) "Bases of polymatroids and problems on graphs," Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 28: No. 4, Article 7. https://doi.org/10.3906/elk-1909-102
Available at: https://journals.tubitak.gov.tr/elektrik/vol28/iss4/7