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.accessioned2015-07-14T23:48:12Z
dc.date.available2015-07-14T23:48:12Z
dc.date.issued2007
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 = (L-0, L-1, E) and a fixed ordering of the nodes in L-0, the problem of finding an ordering of the nodes in L-1 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.sponsorshipPartially supported by TUBITAK-The Scientific and Technological Research Council of Turkey, grant 106E071en_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationÇakiroglu, O. A., Erten, C., Karataş, Ö. & Sözdinler, M. (2007). Crossing minimization in weighted bipartite graphs. Paper presented at the Lecture Notes in Computer Science, 4525, 122-135.en_US
dc.identifier.endpage135
dc.identifier.isbn9783540728443
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.scopus2-s2.0-70349757500
dc.identifier.scopusqualityQ3
dc.identifier.startpage122
dc.identifier.urihttps://hdl.handle.net/11729/646
dc.identifier.volume4525
dc.identifier.wosWOS:000247069500010
dc.identifier.wosqualityQ4
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakConference Proceedings Citation Index – Science (CPCI-S)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.publisherSpringeren_US
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectDrawingsen_US
dc.subjectBipartite graphen_US
dc.subjectEdge densityen_US
dc.subjectWeight balanceen_US
dc.subjectUnweighted graphen_US
dc.subjectUnweighted caseen_US
dc.subjectApproximation algorithmsen_US
dc.subjectComputational complexityen_US
dc.subjectHeuristic algorithmsen_US
dc.subjectOptimizationen_US
dc.subjectPolynomialsen_US
dc.subjectProblem solvingen_US
dc.subjectApproximation ratioen_US
dc.subjectNonnegative weightsen_US
dc.subjectGraph theoryen_US
dc.titleCrossing minimization in weighted bipartite graphsen_US
dc.typeConference Objecten_US
dspace.entity.typePublication

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
646.pdf
Boyut:
545.07 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version
İndir

Koleksiyon

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