Random sampling of Euler tours

被引：6
|
作者：
Tetali, P [1 ]
Vempala, S
机构：
[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
[2] MIT, Dept Math, Cambridge, MA 02139 USA
来源：
ALGORITHMICA | 2001年 / 30卷 / 03期
关键词：
Euler tours; random sampling; random walk;
D O I：
10.1007/s00453-001-0018-6
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We define a Markov chain on the set of Euler tours of a given Eulerian graph based on transformations first defined by Kotzig in 1966. We prove that the chain is rapidly mixing if the maximum degree in the given graph is 6, thus obtaining an efficient algorithm for sampling and counting the set of Euler tours for such an Eulerian graph.
引用
收藏
页码：376 / 385
页数：10
相关论文
共 50 条
  • [1] A One Pass Streaming Algorithm for Finding Euler Tours
    Glazik, Christian
    Schiemann, Jan
    Srivastav, Anand
    THEORY OF COMPUTING SYSTEMS, 2023, 67 (04) : 671 - 693
  • [2] A One Pass Streaming Algorithm for Finding Euler Tours
    Christian Glazik
    Jan Schiemann
    Anand Srivastav
    Theory of Computing Systems, 2023, 67 : 671 - 693
  • [3] Codegree conditions for cycle decompositions and Euler tours in 3-uniform hypergraphs
    Piga, Simon
    Sanhueza-Matamala, Nicolas
    PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, 2021, 195 : 350 - 358
  • [4] Random Sampling with Removal
    Kenneth L. Clarkson
    Bernd Gärtner
    Johannes Lengler
    May Szedlák
    Discrete & Computational Geometry, 2020, 64 : 700 - 733
  • [5] Random Sampling with Removal
    Clarkson, Kenneth L.
    Gartner, Bernd
    Lengler, Johannes
    Szedlak, May
    DISCRETE & COMPUTATIONAL GEOMETRY, 2020, 64 (03) : 700 - 733
  • [6] DISCRETE RANDOM SAMPLING THEORY
    Luo, Chenchi
    McClellan, James H.
    2013 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2013, : 5430 - 5434
  • [7] Hypergraph regularity and random sampling
    Joos, Felix
    Kim, Jaehoon
    Kuhn, Daniela
    Osthus, Deryk
    RANDOM STRUCTURES & ALGORITHMS, 2023, 62 (04) : 956 - 1015
  • [8] Random sampling with fuzzy replacement
    Kesemen, Orhan
    Tiryaki, Bugra Kaan
    Tezel, Ozge
    Ozkul, Eda
    Naz, Ebru
    EXPERT SYSTEMS WITH APPLICATIONS, 2021, 185
  • [9] On Random Sampling in Uniform Hypergraphs
    Czygrinow, Andrzej
    Nagle, Brendan
    RANDOM STRUCTURES & ALGORITHMS, 2011, 38 (04) : 422 - 440
  • [10] Random Flights Related to the Euler - Poisson - Darboux Equation
    Garra, R.
    Orsingher, E.
    MARKOV PROCESSES AND RELATED FIELDS, 2016, 22 (01) : 87 - 110
12345