Exponentialzeit-Algorithmen für Färbbarkeitsprobleme
作者： Frank Gurski , Irene Rothe , Jörg Rothe , Egon Wanke , Frank Gurski
DOI: 10.1007/978-3-642-04500-4_7
关键词:
摘要: Zunachst stellen wir in diesem Abschnitt ein paar Algorithmen vor, die auf einfachen Ideen beruhen und den naiven Algorithmus fur Dreifarbbarkeit bereits schlagen (auch wenn sie naturlich immer noch Exponentialzeit brauchen; schlieslich ist das Dreifarbbarkeitsproblem nach Satz 5.26 NP-vollstandig). Anschliesend gehen kurz Motivation exakte Exponentialzeit-Algorithmen erlautern, weshalb solche Verbesserungen praktische Anwendungen sehr sinnvoll sein konnen.
springer.com
springerlink.com参考文章(29)
Ingo Schiermeyer, Deciding 3-Colourability in Less Than O(1.415^n) Steps workshop on graph theoretic concepts in computer science. pp. 177- 188 ,(1993) , 10.1007/3-540-57899-4_51
Avrim Blum, David Karger, An Õ( n 3/14 )-coloring algorithm for 3-colorable graphs Information Processing Letters. ,vol. 61, pp. 49- 53 ,(1997) , 10.1016/S0020-0190(96)00190-1
David Eppstein, Richard Beigel, 3-coloring in time O (1.3289 n ) Journal of Algorithms. ,vol. 54, pp. 168- 204 ,(2005) , 10.1016/J.JALGOR.2004.06.008
Gerhard J. Woeginger, Exact algorithms for NP-hard problems: a survey Combinatorial optimization - Eureka, you shrink!. pp. 185- 207 ,(2003) , 10.1007/3-540-36478-1_17
Jin-Yi Cai, Gabriele E. Meyer, Graph minimal uncolorability is D P -complete SIAM Journal on Computing. ,vol. 16, pp. 259- 277 ,(1987) , 10.1137/0216022
Venkatesan Guruswami, Sanjeev Khanna, On the Hardness of 4-Coloring a 3-Colorable Graph SIAM Journal on Discrete Mathematics. ,vol. 18, pp. 30- 40 ,(2004) , 10.1137/S0895480100376794
E.L. Lawler, A note on the complexity of the chromatic number problem Information Processing Letters. ,vol. 5, pp. 66- 67 ,(1976) , 10.1016/0020-0190(76)90065-X
Mihalis Yannakakis, Christos H. Papadimitriou, David S. Johnson, On generating all maximal independent sets Information Processing Letters. ,vol. 27, pp. 119- 123 ,(1988) , 10.1016/0020-0190(88)90065-8
David Eppstein, Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction symposium on discrete algorithms. pp. 329- 337 ,(2001) , 10.5555/365411.365471
J. W. Moon, L. Moser, On cliques in graphs Israel Journal of Mathematics. ,vol. 3, pp. 23- 28 ,(1965) , 10.1007/BF02760024