Un ensemble S ? E des arêtes déjà colorées, Une fonction c : S ? {1 ,
S| = 2 alors : Soit xy = E(x)\S l'arête adjacente à x pas encore colorée, Soient {?, ?} = {c(e)|e ? S ? E(x)} et ? = {1, 2, 3}\{?, ?}, Si ? ? {c(e)|e ? S ? E(y)}, alors STOP ; Sinon, c(xy) ? ? ,
est pas un cycle, alors : Choisir un sommet x ? V (F ) tel que d F (z) < 3, Choisir une arête xy ? E(x)\S, Soit {?, ?} = {1, (e)|e ? E(x) ? S}, Soit res = ? un ensemble de fonctions de E(G) ? {1, 2, 3}, Si ? / ? {c(e)|e ? E(y) ? S}, p.3 ,
pour tout x ? V (F ) alors c(E(x) ? S) = ?, alors : Soit {?, ?} = {1, 3}\?, et soit e ? E(F ), Soit res = ? un ensemble de fonctions de E(G) ? {1, p.3 ,
Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics, vol.135, pp.3-16, 2004. ,
Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics, vol.145, issue.1, pp.145-156, 2004. ,
DOI : 10.1016/j.dam.2003.09.004
Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs, Discrete Applied Mathematics, vol.86, issue.2-3, pp.125-144, 1998. ,
DOI : 10.1016/S0166-218X(98)00039-0
On graphs with polynomially solvable maximum-weight clique problem, Networks, vol.10, issue.2, pp.247-253, 1989. ,
DOI : 10.1002/net.3230190206
3-coloring in time, Journal of Algorithms, vol.54, issue.2, pp.168-204, 2005. ,
DOI : 10.1016/j.jalgor.2004.06.008
Dynamic programming and stochastic control processes, Information and Control, vol.1, issue.3, pp.228-239, 1958. ,
DOI : 10.1016/S0019-9958(58)80003-0
Dominating sets for split and bipartite graphs, Information Processing Letters, vol.19, issue.1, pp.37-40, 1984. ,
DOI : 10.1016/0020-0190(84)90126-1
Enumerating the edge-colourings and total colourings of a regular graph, Journal of Combinatorial Optimization, vol.78, issue.3, pp.1-13 ,
DOI : 10.1016/0012-365X(89)90187-8
URL : https://hal.archives-ouvertes.fr/hal-00821598
Exact exponential-time algorithms for finding bicliques, Information Processing Letters, vol.111, issue.2, pp.64-67, 2010. ,
DOI : 10.1016/j.ipl.2010.10.020
URL : https://hal.archives-ouvertes.fr/hal-00535626
Inclusion--Exclusion Algorithms for Counting Set Partitions, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.575-582, 2006. ,
DOI : 10.1109/FOCS.2006.41
Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, pp.546-563, 2009. ,
DOI : 10.1137/070683933
An introduction to chordal graphs and clique trees, Graph Theory and Sparse Matrix Computations, pp.56-57, 1998. ,
A Bottom-Up Method and Fast Algorithms for max independent set, SWAT, pp.62-73, 2010. ,
DOI : 10.1007/978-3-642-13731-0_7
On domination problems for permutation and other graphs, Theoretical Computer Science, vol.54, issue.2-3, pp.181-198, 1987. ,
DOI : 10.1016/0304-3975(87)90128-9
Graph Classes : A Survey, Siam Monographs on Discrete Mathematics and Applications, 1999. ,
DOI : 10.1137/1.9780898719796
Feedback Vertex Set on Graphs of Low Cliquewidth, IWOCA, pp.113-124, 2009. ,
DOI : 10.1007/978-3-642-10217-2_14
URL : https://hal.archives-ouvertes.fr/hal-00555473
The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing , STOC '71, pp.151-158, 1971. ,
DOI : 10.1145/800157.805047
Introduction To Algorithms, 2001. ,
Clustering and domination in perfect graphs, Discrete Applied Mathematics, vol.9, issue.1, pp.27-39, 1984. ,
DOI : 10.1016/0166-218X(84)90088-X
The complexity of generalized clique covering, Discrete Applied Mathematics, vol.22, issue.2, pp.109-118, 1989. ,
DOI : 10.1016/0166-218X(88)90086-8
A Linear Recognition Algorithm for Cographs, SIAM Journal on Computing, vol.14, issue.4, pp.926-934, 1985. ,
DOI : 10.1137/0214065
List coloring in the absence of a linear forest On the parameterized complexity of coloring graphs in the absence of a linear forest, WG, pp.119-130, 2011. ,
Minimal dominating sets in graph classes : Combinatorial bounds and enumeration, SOFSEM, 2012, pp.202-213 ,
Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs, COCOON, pp.2012-133 ,
DOI : 10.1007/978-3-642-32241-9_12
Bicolored independent sets and bicliques, CTW, pp.130-133, 2011. ,
DOI : 10.1016/j.ipl.2012.01.010
On Bipartite and Multipartite Clique Problems, Journal of Algorithms, vol.41, issue.2, pp.388-403, 2001. ,
DOI : 10.1006/jagm.2001.1199
Generating bicliques of a graph in lexicographic order, Theoretical Computer Science, vol.337, issue.1-3, pp.240-248, 2005. ,
DOI : 10.1016/j.tcs.2005.01.014
Hypergraph Transversal Computation and Related Problems in Logic and AI, Lecture Notes in Computer Science, vol.2424, pp.549-564, 2002. ,
DOI : 10.1007/3-540-45757-7_53
Small Maximal Independent Sets and Faster Exact Graph Coloring, Journal of Graph Algorithms and Applications, vol.7, issue.2, pp.131-140, 2003. ,
DOI : 10.7155/jgaa.00064
URL : http://www.cs.brown.edu/publications/jgaa/accepted/2003/Eppstein2003.7.2.pdf
Claw-free graphs ??? A survey, Discrete Mathematics, vol.164, issue.1-3, pp.87-147, 1997. ,
DOI : 10.1016/S0012-365X(96)00045-3
Exact exponential-time algorithms for finding bicliques in a graph, CTW, pp.205-209, 2009. ,
URL : https://hal.archives-ouvertes.fr/hal-00943037
Fixed-parameter complexity of ??-labelings, Discrete Applied Mathematics, vol.113, issue.1, pp.59-72, 2001. ,
DOI : 10.1016/S0166-218X(00)00387-5
Parameterized Complexity Theory, Theoretical Computer Science, 2006. ,
Exact Exponential Algorithms, Texts in Theoretical Computer Science. an EATCS Series, 2010. ,
On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms, Algorithmica, vol.117, issue.2, pp.52-293, 2008. ,
DOI : 10.1007/3-540-36136-7_22
Improved Exact Algorithms for Counting 3- and 4-Colorings, COCOON, pp.65-74, 2007. ,
DOI : 10.1007/978-3-540-73545-8_9
On Two Techniques of Combining Branching and Treewidth, Algorithmica, vol.348, issue.2, pp.54-181, 2009. ,
DOI : 10.1007/978-3-540-28639-4_25
URL : https://hal.archives-ouvertes.fr/lirmm-00399668
A measure & conquer approach for the analysis of exact algorithms, Journal of the ACM, vol.56, issue.5, 2009. ,
DOI : 10.1145/1552285.1552286
Combinatorial bounds via measure and conquer, ACM Transactions on Algorithms, vol.5, issue.1, 2008. ,
DOI : 10.1145/1435375.1435384
Counting Minimum Weighted Dominating Sets, COCOON, pp.165-175, 2007. ,
DOI : 10.1007/978-3-540-73545-8_18
Finding induced subgraphs via minimal triangulations, STACS, pp.383-394, 2010. ,
DOI : 10.1137/140964801
URL : https://hal.archives-ouvertes.fr/inria-00455360
Computers and Intractability : A Guide to the Theory of NP-Completeness, 1979. ,
On independent sets and bicliques in graphs, WG, pp.171-182, 2008. ,
URL : https://hal.archives-ouvertes.fr/hal-00460773
Feedback vertex sets in tournaments, ESA (1), pp.267-277, 2010. ,
Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds, WG, pp.39-50, 2010. ,
DOI : 10.1006/jagm.1996.0061
URL : https://hal.archives-ouvertes.fr/hal-00942919
Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol.57, 2004. ,
Fundamentals of Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, 1998. ,
A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics, vol.10, issue.1, pp.196-210, 1962. ,
DOI : 10.1137/0110015
On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, vol.48, issue.1, pp.92-110, 1990. ,
DOI : 10.1016/0095-8956(90)90132-J
The NP-Completeness of Edge-Coloring, SIAM Journal on Computing, vol.10, issue.4, pp.718-720, 1981. ,
DOI : 10.1137/0210055
A Faster Algorithm for Dominating Set Analyzed by the Potential Method, IPEC, pp.41-54, 2011. ,
DOI : 10.1016/j.jalgor.2004.01.001
On generating all maximal independent sets, Information Processing Letters, vol.27, issue.3, pp.119-123, 1988. ,
DOI : 10.1016/0020-0190(88)90065-8
Enumeration of minimal dominating sets and variants, in FCT, pp.298-309, 2011. ,
Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972. ,
Algorithm Design, 2006. ,
An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.583-590, 2006. ,
DOI : 10.1109/FOCS.2006.11
Improved edge-coloring with three colors, Theoretical Computer Science, vol.410, issue.38-40, pp.3733-3742, 2009. ,
DOI : 10.1016/j.tcs.2009.05.005
Exact Algorithms for L(2,1)-Labeling of Graphs, MFCS, pp.513-524, 2007. ,
DOI : 10.1007/978-3-540-74456-6_46
Domination and total domination on asteroidal triple-free graphs, Discrete Applied Mathematics, vol.99, issue.1-3, pp.111-123, 2000. ,
DOI : 10.1016/S0166-218X(99)00128-6
Domination on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.6, issue.3, pp.400-417, 1993. ,
DOI : 10.1137/0406032
An exact exponential time algorithm for counting bipartite cliques, Information Processing Letters, vol.112, issue.13, pp.535-539, 2012. ,
DOI : 10.1016/j.ipl.2012.04.001
Combinatorial optimization : networks and matroids, 1976. ,
A note on the complexity of the chromatic number problem, Information Processing Letters, vol.5, issue.3, pp.66-67, 1976. ,
DOI : 10.1016/0020-0190(76)90065-X
Algorithmes exacts et exponentiels pour les problèmes NP-difficiles : Domination, variantes et généralisations, 2007. ,
Optimal greedy algorithms for indifference graphs, Computers & Mathematics with Applications, vol.25, issue.7, pp.15-25, 1993. ,
DOI : 10.1016/0898-1221(93)90308-I
Independent sets in extensions of <mml:math altimg="si4.gif" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mn>2</mml:mn><mml:msub><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math>-free graphs, Discrete Applied Mathematics, vol.146, issue.1, pp.74-80, 2005. ,
DOI : 10.1016/j.dam.2004.07.006
New Algorithms for Enumerating All Maximal Cliques, SWAT, pp.260-272, 2004. ,
DOI : 10.1007/978-3-540-27810-8_23
Linear-time recognition of circular-arc graphs, pp.37-93, 2003. ,
Generalizing np-completeness proofs for bipartite graphs and chordal graphs, Department of Mathematical science, Clemson university, Ph.D. Dissertation, 1994. ,
On maximal independent sets of vertices in claw-free graphs, Journal of Combinatorial Theory, Series B, vol.28, issue.3, pp.284-304, 1980. ,
DOI : 10.1016/0095-8956(80)90074-X
On cliques in graphs, Israel Journal of Mathematics, vol.3, issue.1, pp.23-28, 1965. ,
DOI : 10.1007/BF02760024
Randomized Algorithms, 1995. ,
Fast Polynomial-Space Algorithms Using M??bius Inversion: Improving on Steiner Tree and Related Problems, ICALP (1), pp.713-725, 2009. ,
DOI : 10.1007/978-3-540-28639-4_25
Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics And Its Applications, 2006. ,
DOI : 10.1093/acprof:oso/9780198566076.001.0001
Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes, WG, pp.296-307, 2009. ,
DOI : 10.1007/978-3-642-11409-0_26
Counting the number of independent sets in chordal graphs, Journal of Discrete Algorithms, vol.6, issue.2, pp.229-242, 2008. ,
DOI : 10.1016/j.jda.2006.07.006
Paw-free graphs, Information Processing Letters, vol.28, issue.1, pp.53-54, 1988. ,
DOI : 10.1016/0020-0190(88)90143-3
Computational complexity, 1994. ,
The maximum edge biclique problem is NP-complete, Discrete Applied Mathematics, vol.131, issue.3, pp.651-654, 2003. ,
DOI : 10.1016/S0166-218X(03)00333-0
Np-completeness of total and connected domination, and irredundance for bipartite graphs, Department of Mathematical science, Clemson university, 1983. ,
On maximum independent sets in <mml:math altimg="si1.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>-free graphs, Discrete Applied Mathematics, vol.158, issue.9, pp.1041-1044, 2010. ,
DOI : 10.1016/j.dam.2010.01.007
Domination and irredundance in split graphs, Department of Mathematical science, Clemson university, 1983. ,
Indifference graphs, Proof techniques in graph theory, pp.139-146, 1969. ,
Determining the total colouring number is np-hard, Discrete Mathematics, vol.78, issue.3, pp.315-319, 1989. ,
DOI : 10.1016/0012-365X(89)90187-8
On enumerating all minimal solutions of feedback problems, Discrete Applied Mathematics, vol.117, issue.1-3, pp.253-265, 2002. ,
DOI : 10.1016/S0166-218X(00)00339-5
The complexity of computing the permanent, Theoretical Computer Science, vol.8, issue.2, pp.189-201, 1979. ,
DOI : 10.1016/0304-3975(79)90044-6
Exact Exponential-Time Algorithms for Domination Problems in Graphs ,
Inclusion/Exclusion Meets Measure and Conquer, ESA, pp.554-565, 2009. ,
DOI : 10.1007/978-3-642-04128-0_51
On an estimate of the chromatic class of a p-graph, 1964. ,
Introduction to graph theory, 2001. ,
The Design of Approximation Algorithms, 2011. ,
DOI : 10.1017/CBO9780511921735
Exact Algorithms for NP-Hard Problems: A Survey, Combinatorial Optimization -Eureka, You Shrink !, pp.185-208, 2003. ,
DOI : 10.1007/3-540-36478-1_17
The comparability graph of a tree, Proceedings of the American Mathematical Society, pp.189-175, 1962. ,
DOI : 10.1090/S0002-9939-1962-0172273-0
Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.253-264, 1978. ,
DOI : 10.1145/800133.804355
Edge Dominating Sets in Graphs, Society for Industrial and Applied Mathematic, pp.364-372, 1980. ,
DOI : 10.1137/0138030