Search and download archives of mathematical journals

  
 
  Table of contents for this issue | Previous article | Next article
Cameron, Kathie; Edmonds, Jack
Some graphic uses of an even number of odd nodes. Annales de l'institut Fourier, 49 no. 3 (1999), p. 815-827
Full text djvu | pdf | Reviews MR 2000f:05050 | Zbl 0927.05052

stable URL: http://www.numdam.org/item?id=AIF_1999__49_3_815_0

Lookup this article on the publisher's site

Abstract

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.

Bibliography

[1] A. G. THOMASON, Hamilton cycles and uniquely edge-colourable graphs, Annals of Discrete Mathematics, 3 (1978), 259-268.  MR 80e:05077 |  Zbl 0382.05039
[2] S. TOIDA, Properties of an Euler graph, J. Franklin Institute, 295 (1973), 343-345.  MR 48 #10906 |  Zbl 0341.05116
[3] J. A. BONDY and F. Y. HALBERSTAM, Parity theorems for paths and cycles in graphs, J. Graph Theory, 10 (1986), 107-115.  MR 87f:05097 |  Zbl 0594.05041
[4] Kenneth A. BERMAN, Parity results on connected f-factors, Discrete Math., 59 (1986), 1-8.  MR 87f:05127 |  Zbl 0594.05052
[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 80a:05141 |  Zbl 0398.90073
[7] N. J. A. SLOANE, Hamiltonian cycles in a graph of degree 4, J. Combinatorial Theory, 6 (1969), 311-312.  MR 38 #5668 |  Zbl 0176.22402
[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 89h:90083 |  Zbl 0648.90082
[9] Christos H. PAPADIMITRIOU, On the complexity of the local structure of certain convex polytopes, Math. Programming, 14 (1978), 312-324.  Zbl 0376.90067
[10] Kathie CAMERON and Jack EDMONDS, Existentially polytime theorems, DIMACS Series Discrete Mathematics and Theoretical Computer Science, 1 (1990), 83-99.  MR 92i:68043 |  Zbl 0726.68062
[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 95j:68061 |  Zbl 0806.68048
[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 0978.68526
Copyright Cellule MathDoc 2013 | Credit | Site Map