[1]
T. C. Biedl, F.-J. Brandenburg, and X. Deng, Crossings and permutations, in Proceedings of GD 2005 (P. Healy and N. S. Nikolov, eds.), vol. 3843 of LNCS, Springer, 2006, pp. 1-12.
[2]
J. Bartholdi III, C. A. Tovey, and M. A. Trick, Voting schemes for which it can be difficult to tell who won the election, Social Choice and Welfare, vol. 6, pp. 157-165, 1989.
[3]
N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier, and F. A. Rosamond, Fixed-parameter algorithms for Kemeny rankings, Theoretical Computer Science, vol. 410, no. 45, pp. 4554-4570, 2009.
[4]
N. Simjour, Improved parameterized algorithms for the Kemeny aggregation problem, in Proceedings of IWPEC 2009 (J. Chen and F. V. Fomin, eds.), vol. 5917 of LNCS, Springer, 2009, pp. 312-323.
[5]
N. Betzler, J. Guo, and R. Niedermeier, Parameterized computational complexity of Dodgson and Young elections, Information and Computation, vol. 208, no. 2, pp. 165-177, 2010.
[6]
N. Betzler and J. Uhlmann, Parameterized complexity of candidate control in elections and related digraph problems, Theoretical Computer Science, vol. 410, pp. 5425-5442, 2009.
[7]
R. Christian, M. R. Fellows, F. Rosamond, and A. Slinko, On complexity of lobbying in multiple referenda, Review of Economic Design, vol. 11, pp. 217-224, 2007.
[8]
J. McCabe-Dansted, Approximability and computational feasibility of Dodgson’s rule, Master degree dissertation, The University of Auckland, NZ, 2006.
[9]
J. Kemeny, Mathematics without numbers, Daedalus, vol. 88, pp. 571-591, 1959.
[10]
J. Kemeny and J. Snell, Mathematical Models in the Social Sciences. Waltham: Blaisdell Publishing Company, 1962.
[11]
C. Dwork, R. Kumar, M. Naor, and D. Sivakumar, Rank aggregation methods for the web, in Proceedings of the 10th International Conference on World Wide Web, WWW 10, ACM, 2001, pp. 613-622.
[12]
A. Guénoche, B. Vandeputte-Riboud, and J. B. Denis, Selecting varieties using a series of trials and a combinatorial ordering method, Agronomie, vol. 14, pp. 363-375, 1994.
[13]
C. Kenyon-Mathieu and W. Schudy, How to rank with few errors, in Proceedings of STOC 2007, ACM, 2007, pp. 95-103.
[14]
H. Fernau, F. V. Fomin, D. Lokshtanov, M. Mnich, G. Philip, and S. Saurabh, Ranking and drawing in subexponential time, in Combinatorial Algorithms—21st International Workshop, IWOCA 2010, (C. S. Iliopoulos and W. F. Smyth, eds.), vol. 6460 of LNCS, Springer, 2011, pp. 337-348.
[15]
M. Karpinski and W. Schudy, Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament, in Algorithms and Computation—21st International Symposium, ISAAC (1), (O. Cheong, K.-Y. Chwa, and K. Park, eds.), vol. 6506 of LNCS, Springer, 2010, pp. 3-14
[16]
K. Sugiyama, S. Tagawa, and M. Toda, Methods for visual understanding of hierarchical system structures, IEEE Trans. Systems Man Cybernet., vol. 11, no. 2, pp. 109-125, 1981.
[17]
O. Bastert and C. Matuszewski, Layered drawings of digraphs, in Drawing Graphs: Methods and Models, M. Kaufmann and D. Wagner, eds. Springer, 2001, pp. 87-120.
[18]
P. Eades and N. C. Wormald, Edge crossings in drawings of bipartite graphs, Algorithmica, vol. 11, pp. 379-403, 1994.
[19]
X. Muñoz, W. Unger, and I. Vrt’o, One sided crossing minimization is NP-hard for sparse graphs, in Proceedings of GD 2001 (P. Mutzel, M. Jünger, and S. Leipert, eds.), vol. 2265 of LNCS, Springer, 2002, pp. 115-123.
[20]
V. Dujmović, M. R. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. A. Rosamond, M. Suderman, S. Whitesides, and D. R. Wood, A fixed-parameter approach to 2-layer planarization, Algorithmica, vol. 45, pp. 159-182, 2006.
[21]
V. Dujmović, M. R. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. A. Rosamond, S. Whitesides, and D. R. Wood, On the parameterized complexity of layered graph drawing, Algorithmica, vol. 52, no. 2, pp. 267-292, 2008.
[22]
V. Dujmović and S. Whitesides, An efficient fixed parameter tractable algorithm for 1-sided crossing minimization, Algorithmica, vol. 40, pp. 15-32, 2004.
[23]
V. Dujmović, H. Fernau, and M. Kaufmann, Fixed parameter algorithms for one-sided crossing minimization revisited, Journal of Discrete Algorithms, vol. 6, pp. 313-323, 2008.
[24]
H. Fernau, Parameterized algorithms for drawing graphs, in Encyclopedia of Algorithms, M.-Y. Kao, ed. Springer, 2008, pp. 631-635.
[25]
H. Nagamochi, An improved bound on the one-sided minimum crossing number in two-layered drawings, Discrete and Computational Geometry, vol. 33, pp. 569-591, 2005.
[26]
Y. Kobayashi and H. Tamaki, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, in Algorithms—ESA 2012—20th Annual European Symposium (L. Epstein and P. Ferragina, eds.), vol. 7501 of LNCS, Springer, 2012, pp. 683-694.
[27]
F. Baumann, C. Buchheim, and F. Liers, Exact bipartite crossing minimization under tree constraints, in 9th International Symposium on Experimental Algorithms, SEA (P. Festa, ed.), vol. 6049 of LNCS, Springer, 2010, pp. 118-128.
[28]
C. Buchheim and L. Zheng, Fixed linear crossing minimization by reduction to the maximum cut problem, in Computing and Combinatorics, COCOON (D. Z. Chen and D. T. Lee, eds.), vol. 4112 of LNCS, Springer, 2006, pp. 507-516.
[29]
M. Chimani, C. Gutwenger, and P. Mutzel, Experiments on exact crossing minimization using column generation, in Workshop on Experimental Algorithms, WEA (C. Al̀varez and M. Serna, eds.), vol. 4007 of LNCS, Springer, 2006, pp. 303-315.
[30]
M. Chimani and R. Zeranski, Upward planarity testing via SAT, in Graph Drawing 20th International Symposium, GD 2012 (W. Didimo and M. Patrignani, eds.), vol. 7704 of LNCS, Springer, 2013, pp. 248-259.
[31]
G. Gange, P. J. Stuckey, and K. Marriott, Optimal k-level planarization and crossing minimization, in Graph Drawing—18th International Symposium, GD 2010 (U. Brandes and S. Cornelsen, eds.), vol. 6502 of LNCS, Springer, 2011, pp. 238-249.
[32]
M. Jünger and P. Mutzel, 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms, Journal of Graph Algorithms and Applications, vol. 1, pp. 1-25, 1997.
[33]
L. Zheng and C. Buchheim, A new exact algorithm for the two-sided crossing minimization problem, in Combinatorial Optimization and Applications, First International Conference, COCOA (A. W. M. Dress, Y. Xu, and B. Zhu, eds.), vol. 4616 of LNCS, Springer, 2007, pp. 301-310.
[34]
O. A. Çakiroglu, C. Erten, Ö. Karatas, and M. Sözdinler, Crossing minimization in weighted bipartite graphs, in Proceedings of Workshop on Experimental Algorithms, WEA 2007 (C. Demetrescu, ed.), vol. 4525 of LNCS, Springer, 2007, pp. 122-135.
[35]
M. Forster, A fast and simple heuristic for constrained two-level crossing reduction, in Graph Drawing, GD (J. Pach, ed.), vol. 3383 of LNCS, 2004, pp. 206-216.
[36]
M. Forster, Crossings in clustered level graphs, PhD dissertation, Universität Passau, Germany, 2004.
[37]
V. Dujmović, H. Fernau, and M. Kaufmann, Fixed parameter algorithms for one-sided crossing minimization revisited, in Proceedings of GD 2003 (G. Liotta, ed.), vol. 2912 of LNCS, Springer, 2004, pp. 332-344.
[38]
H. Fernau, Parameterized algorithmics: A graph-theoretic approach. Habilitationsschrift, Universität Tübingen, Germany, 2005.
[39]
C. Bachmaier, A radial adaptation of the Sugiyama framework for visualizing hierarchical information, IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 3, pp. 583-594, 2007.
[40]
C. Bachmaier, H. Buchner, M. Forster, and S.-H. Hong, Crossing minimization in extended level drawings of graphs, Discrete Applied Mathematics, vol. 158, pp. 159-179, 2010.
[41]
S. Böcker, F. Hüffner, A. Truß, and M. Wahlström, A faster fixed-parameter approach to drawing binary tanglegrams, in Parameterized and Exact Computation, 4th International Workshop, IWPEC (J. Chen and F. V. Fomin, eds.), vol. 5917 of LNCS, Springer, 2009, pp. 38-49.
[42]
W. Didimo, F. Giordano, and G. Liotta, Upward spirality and upward planarity testing, SIAM J. Discrete Math., vol. 23, no. 4, pp. 1842-1899, 2009.
[43]
H. Fernau, Two-layer planarization: Improving on parameterized algorithmics, Journal of Graph Algorithms and Applications, vol. 9, pp. 205-238, 2005.
[44]
H. Fernau, M. Kaufmann, and M. Poths, Comparing trees via crossing minimization, Journal of Computer and System Sciences, vol. 76, pp. 593-608, 2010.
[45]
J. Uhlmann and M. Weller, Two-layer planarization parameterized by feedback edge set, Theoretical Computer Science, vol. 494, pp. 99-111, 2013.
[46]
J. Alber, H. Fernau, and R. Niedermeier, Parameterized complexity: Exponential speedup for planar graph problems, Journal of Algorithms, vol. 52, pp. 26-56, 2004.
[47]
E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos, Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, Journal of the ACM, vol. 52, no. 6, pp. 866-893, 2005.
[48]
E. D. Demaine and M. Hajiaghayi, The bidimensionality theory and its algorithmic applications, The Computer Journal, vol. 51, no. 3, pp. 292-302, 2008.
[49]
F. Dorn, F. V. Fomin, and D. M. Thilikos, Subexponential parameterized algorithms, Computer Science Review, vol. 2, no. 1, pp. 29-39, 2008.
[50]
F. Dorn, F. V. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh, Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs, in 27th International Symposium on Theoretical Aspects of Computer Science, STACS (J.-Y. Marion and T. Schwentick, eds.), vol. 5 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2010, pp. 251-262.
[51]
F. V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and Y. Villanger, Tight bounds for parameterized complexity of cluster editing, in 30th International Symposium on Theoretical Aspects of Computer Science, STACS (N. Portier and T. Wilke, eds.), vol. 20 of LIPIcs, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2013, pp. 32-43.
[52]
F. V. Fomin and Y. Villanger, Subexponential parameterized algorithm for minimum fill-in, SIAM Journal on Computing, vol. 42, no. 6, pp. 2197-2216, 2013.
[53]
N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: Ranking and clustering, Journal of the ACM, vol. 55, no. 5, pp. 23:1-23:27, 2008.
[54]
N. Alon, D. Lokshtanov, and S. Saurabh, Fast FAST, in Proceedings of ICALP 2009, Part I (S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas, eds.), vol. 5555 of LNCS, Springer, 2009, pp. 49-58.
[55]
U. Feige, Faster fast (feedback arc set in tournaments), Tech. Rep. 0911.5094, ArXiv/CoRR, 2009.
[56]
F. V. Fomin and M. Pilipczuk, Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph, in Algorithms—ESA 2013—21st Annual European Symposium (H. L. Bodlaender and G. F. Italiano, eds.), vol. 8125 of LNCS, Springer, 2013, pp. 505-516.
[57]
J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, Journal of the ACM, vol. 55, no. 5, pp. 21:1-21:19, 2008.
[58]
R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, vol. 63, no. 4, pp. 512-530, 2001.
[59]
J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag, 2006.
[60]
M. Mahajan and V. Raman, Parameterizing above guaranteed values: MaxSat and MaxCut, Journal of Algorithms, vol. 31, no. 2, pp. 335-354, 1999.
[62]
M. Mahajan, V. Raman, and S. Sikdar, Parameterizing above or below guaranteed values, Journal of Computer and System Sciences, vol. 75, no. 2, pp. 137-153, 2009.
[63]
R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Communications, 1972, pp. 85-103.
[64]
S.-H. Hong and H. Nagamochi, New approximation to the one-sided radial crossing minimization, Journal of Graph Algorithms and Applications, vol. 13, no. 2, pp. 179-196, 2009.
AI Chat Paper
