Some graphic uses of an even number of odd nodes

Kathie Cameron; Jack Edmonds

Annales de l'institut Fourier (1999)

  • Volume: 49, Issue: 3, page 815-827
  • ISSN: 0373-0956

Abstract

top
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.

How to cite

top

Cameron, Kathie, and Edmonds, Jack. "Some graphic uses of an even number of odd nodes." Annales de l'institut Fourier 49.3 (1999): 815-827. <http://eudml.org/doc/75365>.

@article{Cameron1999,
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.},
author = {Cameron, Kathie, Edmonds, Jack},
journal = {Annales de l'institut Fourier},
keywords = {parity; hamiltonian; exchange graph; path; tree; flower; lollipop; circuit},
language = {eng},
number = {3},
pages = {815-827},
publisher = {Association des Annales de l'Institut Fourier},
title = {Some graphic uses of an even number of odd nodes},
url = {http://eudml.org/doc/75365},
volume = {49},
year = {1999},
}

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
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 815
EP - 827
AB - 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.
LA - eng
KW - parity; hamiltonian; exchange graph; path; tree; flower; lollipop; circuit
UR - http://eudml.org/doc/75365
ER -

References

top
  1. [1] A. G. THOMASON, Hamilton cycles and uniquely edge-colourable graphs, Annals of Discrete Mathematics, 3 (1978), 259-268. Zbl0382.05039MR80e:05077
  2. [2] S. TOIDA, Properties of an Euler graph, J. Franklin Institute, 295 (1973), 343-345. Zbl0341.05116MR48 #10906
  3. [3] J. A. BONDY and F. Y. HALBERSTAM, Parity theorems for paths and cycles in graphs, J. Graph Theory, 10 (1986), 107-115. Zbl0594.05041MR87f:05097
  4. [4] Kenneth A. BERMAN, Parity results on connected f-factors, Discrete Math., 59 (1986), 1-8. Zbl0594.05052MR87f:05127
  5. [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. [6] Douglas B. WEST, Pairs of adjacent hamiltonian circuits with small intersection, Studies in Applied Math., 59 (1978), 245-248. Zbl0398.90073MR80a:05141
  7. [7] N. J. A. SLOANE, Hamiltonian cycles in a graph of degree 4, J. Combinatorial Theory, 6 (1969), 311-312. Zbl0176.22402MR38 #5668
  8. [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. Zbl0648.90082MR89h:90083
  9. [9] Christos H. PAPADIMITRIOU, On the complexity of the local structure of certain convex polytopes, Math. Programming, 14 (1978), 312-324. Zbl0376.90067
  10. [10] Kathie CAMERON and Jack EDMONDS, Existentially polytime theorems, DIMACS Series Discrete Mathematics and Theoretical Computer Science, 1 (1990), 83-99. Zbl0726.68062MR92i:68043
  11. [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. Zbl0806.68048MR95j:68061
  12. [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. Zbl0978.68526

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.