dc.contributor.author | Çakıroğlu, Olca Arda | en_US |
dc.contributor.author | Erten, Cesim | en_US |
dc.contributor.author | Karataş, Ömer | en_US |
dc.contributor.author | Sözdinler, Melih | en_US |
dc.date.accessioned | 2015-07-14T23:48:12Z | |
dc.date.available | 2015-07-14T23:48:12Z | |
dc.date.issued | 2007 | |
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.isbn | 9783540728443 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.issn | 1611-3349 | |
dc.identifier.uri | https://hdl.handle.net/11729/646 | |
dc.description.abstract | Given 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.sponsorship | Partially supported by TUBITAK-The Scientific and Technological Research Council of Turkey, grant 106E071 | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.rights | info:eu-repo/semantics/closedAccess | en_US |
dc.subject | Drawings | en_US |
dc.subject | Bipartite graph | en_US |
dc.subject | Edge density | en_US |
dc.subject | Weight balance | en_US |
dc.subject | Unweighted graph | en_US |
dc.subject | Unweighted case | en_US |
dc.subject | Approximation algorithms | en_US |
dc.subject | Computational complexity | en_US |
dc.subject | Heuristic algorithms | en_US |
dc.subject | Optimization | en_US |
dc.subject | Polynomials | en_US |
dc.subject | Problem solving | en_US |
dc.subject | Approximation ratio | en_US |
dc.subject | Nonnegative weights | en_US |
dc.subject | Graph theory | en_US |
dc.title | Crossing minimization in weighted bipartite graphs | en_US |
dc.type | conferenceObject | en_US |
dc.description.version | Publisher's Version | en_US |
dc.relation.journal | Lecture Notes in Computer Science | en_US |
dc.contributor.department | Işık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü | en_US |
dc.contributor.department | Işık University, Faculty of Engineering, Department of Computer Engineering | en_US |
dc.contributor.authorID | 0000-0002-8149-7113 | |
dc.identifier.volume | 4525 | |
dc.identifier.startpage | 122 | |
dc.identifier.endpage | 135 | |
dc.peerreviewed | Yes | en_US |
dc.publicationstatus | Published | en_US |
dc.relation.publicationcategory | Konferans Öğesi - Uluslararası - Kurum Öğretim Elemanı | en_US |
dc.contributor.institutionauthor | Çakıroğlu, Olca Arda | en_US |
dc.contributor.institutionauthor | Erten, Cesim | en_US |
dc.contributor.institutionauthor | Karataş, Ömer | en_US |
dc.contributor.institutionauthor | Sözdinler, Melih | en_US |
dc.relation.index | WOS | en_US |
dc.relation.index | Scopus | en_US |
dc.relation.index | Conference Proceedings Citation Index – Science (CPCI-S) | en_US |
dc.description.quality | Q4 | |
dc.description.wosid | WOS:000247069500010 | |