no. 3
Some graphic uses of an even number of odd nodes
Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 815-827.

La parité des degrés dans les grands graphes d’échanges implicites implique des théorèmes EP qui assurent l’existence d’un second objet, sans assurer d’une manière évidente un algorithme polynomial pour trouver cet objet.

Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.

@article{AIF_1999__49_3_815_0,
     author = {Cameron, Kathie and Edmonds, Jack},
     title = {Some graphic uses of an even number of odd nodes},
     journal = {Annales de l'Institut Fourier},
     pages = {815--827},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     doi = {10.5802/aif.1694},
     mrnumber = {2000f:05050},
     zbl = {0927.05052},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/aif.1694/}
}
TY  - JOUR
AU  - Cameron, Kathie
AU  - Edmonds, Jack
TI  - Some graphic uses of an even number of odd nodes
JO  - Annales de l'Institut Fourier
PY  - 1999
SP  - 815
EP  - 827
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.1694/
DO  - 10.5802/aif.1694
LA  - en
ID  - AIF_1999__49_3_815_0
ER  - 
%0 Journal Article
%A Cameron, Kathie
%A Edmonds, Jack
%T Some graphic uses of an even number of odd nodes
%J Annales de l'Institut Fourier
%D 1999
%P 815-827
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U http://www.numdam.org/articles/10.5802/aif.1694/
%R 10.5802/aif.1694
%G en
%F AIF_1999__49_3_815_0
Cameron, Kathie; Edmonds, Jack. Some graphic uses of an even number of odd nodes. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 815-827. doi : 10.5802/aif.1694. http://www.numdam.org/articles/10.5802/aif.1694/

[1] A. G. Thomason, Hamilton cycles and uniquely edge-colourable graphs, Annals of Discrete Mathematics, 3 (1978), 259-268. | MR | Zbl

[2] S. Toida, Properties of an Euler graph, J. Franklin Institute, 295 (1973), 343-345. | MR | Zbl

[3] J. A. Bondy and F. Y. Halberstam, Parity theorems for paths and cycles in graphs, J. Graph Theory, 10 (1986), 107-115. | MR | Zbl

[4] Kenneth A. Berman, Parity results on connected f-factors, Discrete Math., 59 (1986), 1-8. | MR | Zbl

[5] Kathie Cameron, Krawczyk's graphs show Thomason's algorithm for finding a second Hamilton cycle through a given edge in a cubic graph is exponential, Fifth Czech-Slovak Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague; SIAM Conference on Discrete Mathematics, Toronto; July 1998.

[6] Douglas B. West, Pairs of adjacent hamiltonian circuits with small intersection, Studies in Applied Math., 59 (1978), 245-248. | MR | Zbl

[7] N. J. A. Sloane, Hamiltonian cycles in a graph of degree 4, J. Combinatorial Theory, 6 (1969), 311-312. | MR | Zbl

[8] M. Chrobak and S. Poljak, On common edges in optimal solutions to traveling salesman and other optimization problems, Discrete Applied Math., 20 (1988), 101-111. | MR | Zbl

[9] Christos H. Papadimitriou, On the complexity of the local structure of certain convex polytopes, Math. Programming, 14 (1978), 312-324. | Zbl

[10] Kathie Cameron and Jack Edmonds, Existentially polytime theorems, DIMACS Series Discrete Mathematics and Theoretical Computer Science, 1 (1990), 83-99. | MR | Zbl

[11] Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Computer and System Sci., 48 (1994), 498-532. | MR | Zbl

[12] Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi, The relative complexity of NP search problems, Proc. 27 th ACM STOC (1995), 303-314. | Zbl

Cité par Sources :