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.

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.