scientific article; zbMATH DE number 549852

MaRDI QIDQ4287356zbMATH OpenFDO

Authors József Beck

Publication date 2 January 1995

zbMATH Keywords

big monochromatic complete subgraphscomplete graphcomplexityedge coloringexponential lower boundmatchingparallel matching complexityRamsey's theorem

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Combinatorics in computer science (68R05) Distributed algorithms (68W15)

Recommendations

• Publication:3201758
• Approximating matchings in parallel
• Complexity results for rainbow matchings
• Parameterized complexity of perfectly matched sets
• On parallel complexity of maximum \(f\)-matching and the degree sequence problem
• A note on parallel complexity of maximum f-matching
• Complexity of Ramsey null sets
• scientific article; zbMATH DE number 54587
• On the uniform computational content of Ramsey's theorem
• Computational complexity of simultaneous elementary matching problems

Cited in

(5)

• Applications of Ramsey's theorem to decision tree complexity
• White-box vs. black-box complexity of search problems: Ramsey and graph property testing
• REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM
• Graph Ramsey theory and the polynomial hierarchy
• Graph Ramsey theory and the polynomial hierarchy

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4287356)