Extensions of k -subsets to k + 1 -subsets - existence versus constructability

Svatopluk Poljak; Daniel Turzík; Pavel Pudlák

Commentationes Mathematicae Universitatis Carolinae (1982)

  • Volume: 023, Issue: 2, page 337-349
  • ISSN: 0010-2628

How to cite

top

Poljak, Svatopluk, Turzík, Daniel, and Pudlák, Pavel. "Extensions of $k$-subsets to $k+1$-subsets - existence versus constructability." Commentationes Mathematicae Universitatis Carolinae 023.2 (1982): 337-349. <http://eudml.org/doc/17184>.

@article{Poljak1982,
author = {Poljak, Svatopluk, Turzík, Daniel, Pudlák, Pavel},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {algorithms; relations between decision and construction problems; polynomial time; finite set; Hamiltonian cycles},
language = {eng},
number = {2},
pages = {337-349},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Extensions of $k$-subsets to $k+1$-subsets - existence versus constructability},
url = {http://eudml.org/doc/17184},
volume = {023},
year = {1982},
}

TY - JOUR
AU - Poljak, Svatopluk
AU - Turzík, Daniel
AU - Pudlák, Pavel
TI - Extensions of $k$-subsets to $k+1$-subsets - existence versus constructability
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1982
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 023
IS - 2
SP - 337
EP - 349
LA - eng
KW - algorithms; relations between decision and construction problems; polynomial time; finite set; Hamiltonian cycles
UR - http://eudml.org/doc/17184
ER -

References

top
  1. T. BAKER J. GILL R. SOLOVAY, Relativizations of the P = ? N P question, SIAM J. Comp. Vol. 4 (1975), 431-442. (1975) MR0395311
  2. C. BERGE, Graphs and Hypergraphs, North-Holland, Amsterdam (1973). (1973) Zbl0254.05101MR0357172
  3. J. A. BONDY V. CHVÁTAL, A method in graph theory, Discrete Mathematica 16 (1976), 111-135. (1976) MR0414429
  4. V. CHVÁTAL, On Hamiltonian's ideals, Jouгnal of Combinatorial Theory 12 (1972), 163-168. (1972) MR0294155
  5. J. E. HOPCROFT R. M. KARP, Ann n 5 / 2 Algorithm for Maximal Matchings in Bipartite Gгaphs, SIAM J. Comp. Vol. 2 (1973), 225-231. (1973) MR0337699
  6. C. P. SCHNORR, Optimal algoгithms for self-reducible problems, Automata, Languages and Programming 1976, Eds.: S. Michaelson and R. Milner, University Press Edinburgh, 322-337. (1976) 
  7. A. G. THOMASOM, Hamiltonian cycles and uniquely edge colourable graphs, Advances in Graph Theoгy B. Bollobás, ed., Annals of Discrete Mathematics 3 (1976), 259-268. (1976) MR0499124
  8. C. GREENE D. J. KLEITMAN, Pгoof techniques in the theory of finite sets, Studies in Combinatorics, pp. 22-79, MAA Studles in Math. 17, Math. Assoc. America, Washington, D.C., 1978. (1978) MR0513002

NotesEmbed ?

top

You must be logged in to post comments.