A Markov chain on the solution space of edge colorings of bipartite graphs

DOI10.1016/j.dam.2023.01.029OpenAlexW4319067239MaRDI QIDQ2696608

István Miklós, Letong Hong

Publication date: 17 April 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.11990

zbMATH Keywords

Latin squaresMetropolis-Hastings algorithmMCMCedge colorings

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15)

Uses Software

• Stony Brook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Random generation of combinatorial structures from a uniform distribution
• Planar graphs of maximum degree seven are Class I
• Half-regular factorizations of the complete bipartite graph
• The NP-Completeness of Edge-Coloring
• On Edge Coloring Bipartite Graphs
• Generating uniformly distributed random latin squares
• Markov Chains
• Short Shop Schedules
• Handbook of Graph Theory
• Computational Complexity of Counting and Sampling
• NP completeness of finding the chromatic index of regular graphs
• Edge-Coloring Bipartite Graphs
• Equation of State Calculations by Fast Computing Machines
• Monte Carlo sampling methods using Markov chains and their applications
• The complexity of path coloring and call scheduling

This page was built for publication: A Markov chain on the solution space of edge colorings of bipartite graphs