Some graphic uses of an even number of odd nodes
Annales de l'institut Fourier (1999)
- Volume: 49, Issue: 3, page 815-827
- ISSN: 0373-0956
Access Full Article
topAbstract
topHow to cite
topCameron, 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] A. G. THOMASON, Hamilton cycles and uniquely edge-colourable graphs, Annals of Discrete Mathematics, 3 (1978), 259-268. Zbl0382.05039MR80e:05077
- [2] S. TOIDA, Properties of an Euler graph, J. Franklin Institute, 295 (1973), 343-345. Zbl0341.05116MR48 #10906
- [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] Kenneth A. BERMAN, Parity results on connected f-factors, Discrete Math., 59 (1986), 1-8. Zbl0594.05052MR87f:05127
- [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. Zbl0398.90073MR80a:05141
- [7] N. J. A. SLOANE, Hamiltonian cycles in a graph of degree 4, J. Combinatorial Theory, 6 (1969), 311-312. Zbl0176.22402MR38 #5668
- [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] Christos H. PAPADIMITRIOU, On the complexity of the local structure of certain convex polytopes, Math. Programming, 14 (1978), 312-324. Zbl0376.90067
- [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] 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] 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 ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.