Bases of polymatroids and problems on graphs
Küçük Resim Yok
Tarih
2020
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Tubitak Scientific & Technological Research Council Turkey
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
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.
Açıklama
Anahtar Kelimeler
Submodular function, bases of polymatroid, hamiltonian path and circuit, traveling salesman problem
Kaynak
Turkish Journal of Electrical Engineering and Computer Sciences
WoS Q Değeri
Q4
Scopus Q Değeri
Q3
Cilt
28
Sayı
4