Bases of polymatroids and problems on graphs

Basit Öğe Kaydı
dc.authoridKutucu, Hakan/0000-0001-7144-7246
dc.contributor.authorKutucu, Hakan
dc.date.accessioned2024-09-29T16:08:20Z
dc.date.available2024-09-29T16:08:20Z
dc.date.issued2020
dc.departmentKarabük Üniversitesien_US
dc.description.abstractIn 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.en_US
dc.identifier.doi10.3906/elk-1909-102
dc.identifier.endpage1915en_US
dc.identifier.issn1300-0632
dc.identifier.issn1303-6203
dc.identifier.issue4en_US
dc.identifier.scopus2-s2.0-85090148783en_US
dc.identifier.scopusqualityQ3en_US
dc.identifier.startpage1905en_US
dc.identifier.trdizinid513535en_US
dc.identifier.urihttps://doi.org/10.3906/elk-1909-102
dc.identifier.urihttps://search.trdizin.gov.tr/tr/yayin/detay/513535
dc.identifier.urihttps://hdl.handle.net/20.500.14619/7496
dc.identifier.volume28en_US
dc.identifier.wosWOS:000553765600007en_US
dc.identifier.wosqualityQ4en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakTR-Dizinen_US
dc.language.isoenen_US
dc.publisherTubitak Scientific & Technological Research Council Turkeyen_US
dc.relation.ispartofTurkish Journal of Electrical Engineering and Computer Sciencesen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectSubmodular functionen_US
dc.subjectbases of polymatroiden_US
dc.subjecthamiltonian path and circuiten_US
dc.subjecttraveling salesman problemen_US
dc.titleBases of polymatroids and problems on graphsen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu
TR-Dizin İndeksli Yayınlar Koleksiyonu