An algorithmic embedding of graphs via perfect matchings

DOI10.1007/3-540-49543-6_3MaRDI QIDQ4247195zbMATH OpenFDO

Authors Vojtěch Rödl, Andrzej Ruciński, Michelle Wagner

Publication date 13 December 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49543-6_3

zbMATH Keywords

algorithmic embeddingblow-up lemmaderandomizationErdős-Selfridge methodprobabilistic argument

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An algorithmic version of the blow-up lemma
• The Blow-up Lemma
• Matchings meeting quotas and their impact on the blow-up lemma

Cited in

(7)

• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Algorithms for graphs embeddable with few crossings per edge
• Matchings meeting quotas and their impact on the blow-up lemma
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• The Blow-up Lemma
• An extension of the blow-up lemma to arrangeable graphs
• Fundamentals of Computation Theory

This page was built for publication: An algorithmic embedding of graphs via perfect matchings

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