On the complexity of crossings in permutations

DOI10.1016/J.DISC.2007.12.088zbMath1173.05003OpenAlexW2029352747MaRDI QIDQ1011761

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

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 minimizationrank aggregationKendall-\(\tau \) distanceNP-hardness approximations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Planar graphs; geometric and topological aspects of graph theory (05C10) Social choice (91B14) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (14)

Ranking chain sum orders ⋮ Studies in Computational Aspects of Voting ⋮ The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders ⋮ Privacy in Elections: k-Anonymizing Preference Orders ⋮ A unifying rank aggregation framework to suitably and efficiently aggregate any kind of rankings ⋮ On weakly and strongly popular rankings ⋮ Computing kemeny rankings from \(d\)-Euclidean preferences ⋮ On the computation of median linear orders, of median complete preorders and of median weak orders ⋮ On graphs associated to sets of rankings ⋮ The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders ⋮ On the hardness of maximum rank aggregation problems ⋮ \(k\)-majority digraphs and the hardness of voting with a constant number of voters ⋮ Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation ⋮ COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES

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

This page was built for publication: On the complexity of crossings in permutations