On the complexity of crossings in permutations

DOI10.1016/j.disc.2007.12.088zbMath1173.05003MaRDI QIDQ1011761

Xiaotie Deng, Therese C. Biedl, Franz-Josef Brandenburg

Publication date: 9 April 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2007.12.088

zbMATH Keywords

crossing minimization; rank aggregation; Kendall-\(\tau \) distance; NP-hardness approximations

Mathematics Subject Classification ID

05A05: Permutations, words, matrices

05C10: Planar graphs; geometric and topological aspects of graph theory

91B14: Social choice

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

On the computation of median linear orders, of median complete preorders and of median weak orders, The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders, COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES, Studies in Computational Aspects of Voting, The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Median linear orders: Heuristics and a branch and bound algorithm
• Voting schemes for which it can be difficult to tell who won the election
• Edge crossings in drawings of bipartite graphs
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximate and dynamic rank aggregation
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Crossing Number is NP-Complete
• `` Strong NP-Completeness Results
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• Breaking cycles for minimizing crossings
• Aggregating inconsistent information
• Drawing graphs. Methods and models