Algorithms for finding maximum transitive subtournaments

详细信息    查看全文

• 作者：Lasse Kiviluoto ; Patric R. J. Östergård…
• 关键词：Backtrack search ; Clique ; Directed acyclic graph ; Feedback vertex set ; Russian doll search ; Transitive tournament
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：31
• 期：2
• 页码：802-814
• 全文大小：457 KB
• 参考文献：Alon N (1998) On the capacity of digraphs. Eur J Combin 19:1–5CrossRef MATH
  Bang-Jensen J, Gutin G (2001) Digraphs: theory, algorithms and applications. Springer, London
  Berghammer R, Fronk A (2006) Exact computation of minimum feedback vertex sets with relational algebra. Fund Inform 70:301–316MathSciNet MATH
  Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. In: Du D-Z, Pardalos PM (eds) Handbook of combinatorial optimization, supplement vol A. Kluwer, Dordrecht, pp 1–74
  Brazdil PB, Soares C (2000) A comparison of ranking methods for classification algorithm selection. In: López de Mántanas R, Plaza E (eds) Machine learning: ECML 2000, LNCS vol 1810. Springer, Berlin, pp 63–74
  Butenko S, Wilhelm WE (2006) Clique-detection models in computational biochemistry and genomics. Eur J Oper Res 173:1–17MathSciNet CrossRef MATH
  Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9:375–382CrossRef MATH
  Chakradhar ST, Balakrishnan A, Agrawal VD (1995) An exact algorithm for selecting partial scan flip-flops. J Electron Test Theory Appl 7:83–93CrossRef
  Cong J, Smith M (1993) A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design. In: Proceedings of the 30th international design automation conference. ACM, New York, pp 755–760
  Dechter R (2003) Constraint processing. Morgan Kaufmann, San Francisco
  Funke M, Reinelt G (1996) A polyhedral approach to the feedback vertex set problem. In: Cunningham WH, McCormick ST, Queyranne M (eds) Integer programming and combinatorial optimization, LNCS vol 1084. Springer, Berlin, pp 445–459
  Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H Freeman, San FranciscoMATH
  Gargano L, Körner J, Vaccaro U (1992) Qualitative independence and Sperner problems for directed graphs. J Combin Theory Ser A 61:173–192MathSciNet CrossRef MATH
  Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85–103
  Kiviluoto L, Östergård PRJ, Vaskelainen VP (2009) Sperner capacity of small digraphs. Adv Math Commun 3:125–133MathSciNet CrossRef MATH
  Körner J, Pilotto C, Simonyi G (2005) Local chromatic number and Sperner capacity. J Combin Theory Ser B 95:101–117MathSciNet CrossRef MATH
  Lam CWH, Thiel LH, Swiercz S (1988) A computer search for a projective plane of order 10. In: Deza MM, Frankl P, Rosenberg IG (eds) Algebraic, extremal and metric combinatorics. Cambridge University Press, Cambridge, pp 155–165
  Lin H-M, Jou J-Y (2000) On computing the minimum feedback vertex set of a directed graph by contraction operations. IEEE Trans Comput-Aided Design Integr Circuits Syst 19:295–307
  Lloyd EL, Soffa ML (1988) On locating minimum feedback vertex sets. J Comput Syst Sci 37:292–311MathSciNet CrossRef MATH
  McGeoch CC (2007) Experimental algorithmics. Commun ACM 50(11):27–31CrossRef
  Neumann-Lara V (1982) The dichromatic number of a digraph. J Combin Theory Ser B 33:265–270MathSciNet CrossRef MATH
  Orenstein T, Kohavi Z, Pomeranz I (1995) An optimal algorithm for cycle breaking in directed graphs. J Electron Test Theory Appl 7:71–81CrossRef
  Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl Math 120:197–207
  Östergård PRJ, Vaskelainen VP (2011) Russian doll search for the Steiner triple covering problem. Optim Lett 5:631–638MathSciNet CrossRef MATH
  Pardalos PM, Xue J (1994) The maximum clique problem. J Global Optim 4:301–328MathSciNet CrossRef MATH
  Rhodes N, Willett P, Calvet A, Dunbar JB, Humblet C (2003) CLIP: similarity searching of 3D databases using clique detection. J Chem Inform Comput Sci 43:443–448CrossRef
  Sali A, Simonyi G (1999) Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities. Eur J Combin 20:93–99MathSciNet CrossRef MATH
  Shannon CE (1956) The zero-error capacity of a noisy channel. IRE Trans Inform Theory 2:8–19MathSciNet CrossRef
  Smith GW Jr, Walford RB (1975) The identification of a minimal feedback vertex set of a directed graph. IEEE Trans Circuits Syst 22:9–14MathSciNet CrossRef
  Thiel LH, Lam CWH, Swiercz S (1987) Using a CRAY-1 to perform backtrack search. In: Kartashev LP, Kartashev SI (eds) Supercomputing ’87: supercomputer design, performance evaluation and performance education, vol 3. International Supercomputing Institute, St. Petersburg, FL, pp 92–99
  Verfaillie G, Lemaître M, Schiex T (1996) Russian doll search for solving constraint optimization problems. In: Proceedings of the 13th national conference on artificial intelligence (AAAI-96). AAAI Press, Menlo Park, pp 181–187
  
• 作者单位：Lasse Kiviluoto (1)
  Patric R. J. Östergård (2)
  Vesa P. Vaskelainen (2)
  
  1. Speago Ltd, Pieni Roobertinkatu 11, 00130, Helsinki, Finland
  2. Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076, Aalto, Finland
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

The problem of finding a maximum clique is a fundamental problem for undirected graphs, and it is natural to ask whether there are analogous computational problems for directed graphs. Such a problem is that of finding a maximum transitive subtournament in a directed graph. A tournament is an orientation of a complete graph; it is transitive if the occurrence of the arcs \(xy\) and \(yz\) implies the occurrence of \(xz\). Searching for a maximum transitive subtournament in a directed graph \(D\) is equivalent to searching for a maximum induced acyclic subgraph in the complement of \(D\), which in turn is computationally equivalent to searching for a minimum feedback vertex set in the complement of \(D\). This paper discusses two backtrack algorithms and a Russian doll search algorithm for finding a maximum transitive subtournament, and reports experimental results of their performance. Keywords Backtrack search Clique Directed acyclic graph Feedback vertex set Russian doll search Transitive tournament