首页 | 本学科首页   官方微博 | 高级检索  
     

Social Choice Meets Graph Drawing: How to Get Subexponential Time Algorithms for Ranking and Drawing Problems
基金项目:supported by a GermanNorwegian PPP grant; supported by the Indo-German Max Planck Center for Computer Science (IMPECS)
摘    要:We analyze a common feature of p-Kemeny AGGregation(p-KAGG) and p-One-Sided Crossing Minimization(p-OSCM) to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O.2O.pk logk//,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural above-guarantee versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of votes in the input to p-KAGG is odd the above guarantee version can still be solved in time O.2O.pk logk//, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails(equivalently, unless FPT D M[1]).

关 键 词:社会选择理论  时间算法  图形图像  绘图  运行时间  图形绘制  版本  最小化
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号