New bounds on the barycenter heuristic for bipartite graph drawing

Autor:	Matthias F. Stallmann, Xiao Yu Li
Rok vydání:	2002
Předmět:	Discrete mathematics Minimization problem Graph Computer Science Applications Theoretical Computer Science Combinatorics Performance ratio Graph drawing Signal Processing Bipartite graph Edge crossing Minification Connectivity Information Systems Mathematics
Zdroj:	Information Processing Letters. 82:293-298
ISSN:	0020-0190
DOI:	10.1016/s0020-0190(01)00297-6
Popis:	The barycenter heuristic is often used to solve the NP-hard two-layer edge crossing minimization problem. It is well known that the barycenter heuristic can give solutions as bad as Ω( n ) times the optimum, where n is the number of nodes in the graph. However, the example used in the proof has many isolated nodes. Makinen [EATCS Bull. 70 (2000) 156–158] conjectured that a better performance ratio is possible if isolated nodes are not present. We show that the performance ratio for the barycenter heuristic is still Ω( n ) even for connected bipartite graphs. We also prove a tight constant ratio for the barycenter heuristic on bounded-degree graphs. The performance ratio is d−1, where d is the maximum degree of a node in the layer that can be permuted.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::7128adfb8ba21db041d7917cda580455 https://doi.org/10.1016/s0020-0190(01)00297-6 Zobrazit plný text záznamu Full Text from ScienceDirect