On the complexity of crossings in permutations
type: Item
instance of: scholarly article
title: On the complexity of crossings in permutations
zbMATH Open document ID: 1173.05003
author: Xiaotie Deng
author: Therese Biedl
author: Franz J. Brandenburg
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 91B14
zbMATH DE Number: 5542411
zbMATH Keywords: crossing minimization
zbMATH Keywords: rank aggregation
zbMATH Keywords: Kendall-\(\tau \) distance
zbMATH Keywords: NP-hardness approximations
MaRDI profile type: Publication
full work available at URL: j.disc.2007.12.088
OpenAlex ID: W2029352747
cites work: Aggregating inconsistent information
cites work: Median linear orders: Heuristics and a branch and bound algorithm
cites work: Voting schemes for which it can be difficult to tell who won the election
cites work: Approximate and dynamic rank aggregation
cites work: Breaking cycles for minimizing crossings
cites work: Q4153936
cites work: Q3154375
cites work: Edge crossings in drawings of bipartite graphs
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: `` Strong '' NP-Completeness Results
cites work: Crossing Number is NP-Complete
cites work: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
cites work: Drawing graphs. Methods and models
cites work: Q3043710
cites work: Q5585195
cites work: An improved bound on the one-sided minimum crossing number in two-layered drawings
cites work: Q3992847
DOI: 10.1016/J.DISC.2007.12.088
description: scientific article; zbMATH DE number 5542411