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 条
  • [41] Fast LMNN Algorithm Through Random Sampling
    Wu, Kaiyuan
    Zheng, Zhiming
    2015 IEEE INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOP (ICDMW), 2015, : 871 - 876
  • [42] RANDOM SAMPLING FOR DISTRIBUTED CODED MATRIX MULTIPLICATION
    Chang, Wei-Ting
    Tandon, Ravi
    2019 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2019, : 8187 - 8191
  • [43] Motion analysis by random sampling and voting process
    Imiya, A
    Fermin, I
    COMPUTER VISION AND IMAGE UNDERSTANDING, 1999, 73 (03) : 309 - 328
  • [44] Neuroelectric source localization by random spatial sampling
    Pitolli, F.
    Pocci, C.
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2016, 296 : 237 - 246
  • [45] Weighted Jump in Random Walk graph sampling
    Qi, Xiao
    NEUROCOMPUTING, 2024, 586
  • [46] AN IMPROVED ALGORITHM FOR ORDERED SEQUENTIAL RANDOM SAMPLING
    NAIR, KA
    ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1990, 16 (03): : 269 - 274
  • [47] Signal reconstruction by random sampling in chirp space
    Eric Carlen
    R. Vilela Mendes
    Nonlinear Dynamics, 2009, 56
  • [48] PGMJoins: Random Join Sampling with Graphical Models
    Shanghooshabad, Ali Mohammadi
    Kurmanji, Meghdad
    Ma, Qingzhi
    Shekelyan, Michael
    Almasi, Mehrdad
    Triantafillou, Peter
    SIGMOD '21: PROCEEDINGS OF THE 2021 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2021, : 1610 - 1622
  • [49] Attribute Reduction Based on Lift and Random Sampling
    Chen, Qing
    Xu, Taihua
    Chen, Jianjun
    SYMMETRY-BASEL, 2022, 14 (09):
  • [50] Counting Triangles in Large Graphs by Random Sampling
    Wu, Bin
    Yi, Ke
    Li, Zhenguo
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2016, 28 (08) : 2013 - 2026
12345