Crossing minimization in weighted bipartite graphs

Basit Öğe Kaydı
dc.authorid0000-0002-8149-7113
dc.contributor.authorÇakıroğlu, Olca Ardaen_US
dc.contributor.authorErten, Cesimen_US
dc.contributor.authorKarataş, Ömeren_US
dc.contributor.authorSözdinler, Melihen_US
dc.date.accessioned2020-12-29T10:04:40Z
dc.date.available2020-12-29T10:04:40Z
dc.date.issued2009-12
dc.departmentIşık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.departmentIşık University, Faculty of Engineering, Department of Computer Engineeringen_US
dc.description.abstractGiven a bipartite graph G = (L0, L1, E) and a fixed ordering of the nodes in L0, the problem of finding an ordering of the nodes in L1 that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances.en_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationÇakiroglu, O. A., Erten, C., Karataş, Ö. & Sözdinler, M. (2009). Crossing minimization in weighted bipartite graphs. Journal of Discrete Algorithms, 7(4), 439-452. doi:10.1016/j.jda.2008.08.003en_US
dc.identifier.doi10.1016/j.jda.2008.08.003
dc.identifier.endpage452
dc.identifier.issn1570-8667
dc.identifier.issn1570-8675
dc.identifier.issue4
dc.identifier.scopus2-s2.0-70349757500
dc.identifier.scopusqualityN/A
dc.identifier.startpage439
dc.identifier.urihttps://hdl.handle.net/11729/2999
dc.identifier.urihttp://dx.doi.org/10.1016/j.jda.2008.08.003
dc.identifier.volume7
dc.identifier.wosWOS:000213947000007
dc.identifier.wosqualityN/A
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakEmerging Sources Citation Index (ESCI)en_US
dc.institutionauthorÇakıroğlu, Olca Ardaen_US
dc.institutionauthorErten, Cesimen_US
dc.institutionauthorKarataş, Ömeren_US
dc.institutionauthorSözdinler, Melihen_US
dc.institutionauthorid0000-0002-8149-7113
dc.language.isoenen_US
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.publisherElsevier B.V.en_US
dc.relation.ispartofJournal of Discrete Algorithmsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectPlanarityen_US
dc.subjectGraph drawingen_US
dc.subjectCrossing minimizationen_US
dc.subjectApproximation algorithmsen_US
dc.subjectCombinatorial optimizationen_US
dc.subjectWeighted bipartite graphsen_US
dc.subjectApproximation ratiosen_US
dc.subjectBipartite graphsen_US
dc.subjectGraph layouten_US
dc.subjectNP Completeen_US
dc.subjectPolynomial-time algorithmsen_US
dc.subjectCrossings (pipe and cable)en_US
dc.subjectGraph theoryen_US
dc.subjectHeuristic methodsen_US
dc.subjectPolynomial approximationen_US
dc.titleCrossing minimization in weighted bipartite graphsen_US
dc.typeArticleen_US
dspace.entity.typePublication

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
2999.pdf
Boyut:
326.88 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version
İndir
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
license.txt
Boyut:
1.44 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama:
İndir

Koleksiyon

Makale Koleksiyonu | Bilgisayar Mühendisliği Bölümü
Scopus İndeksli Yayınlar Koleksiyonu
WoS İndeksli Yayınlar Koleksiyonu