Bases of polymatroids and problems on graphs

Küçük Resim Yok

Tarih

2020

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

Künye