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 条
  • [31] Signal reconstruction by random sampling in chirp space
    Carlen, Eric
    Mendes, R. Vilela
    NONLINEAR DYNAMICS, 2009, 56 (03) : 223 - 229
  • [32] Random Sampling and performance analysis for Networked Systems
    Lu, Zibao
    Zhuang, Yan
    Yuan, Lei
    PROCEEDINGS OF THE 36TH CHINESE CONTROL CONFERENCE (CCC 2017), 2017, : 7847 - 7851
  • [33] Biased Random Walk Sampling on Assortative Networks
    Yook, Soon-Hyung
    Yun, Yeo-kwang
    Kim, Yup
    JOURNAL OF THE KOREAN PHYSICAL SOCIETY, 2010, 56 (03) : 990 - 993
  • [34] Distinct Random Sampling from a Distributed Stream
    Chung, Yung-Yu
    Tirthapura, Srikanta
    2015 IEEE 29TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS), 2015, : 532 - 541
  • [35] Spectral estimation for diffusions with random sampling times
    Chorowski, Jakub
    Trabs, Mathias
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2016, 126 (10) : 2976 - 3008
  • [36] COVARIANCE TRACKING WITH FORGETTING FACTOR AND RANDOM SAMPLING
    Zhang, Xuguang
    Li, Xiaoli
    Liang, Ming
    Wang, Yanjie
    INTERNATIONAL JOURNAL OF UNCERTAINTY FUZZINESS AND KNOWLEDGE-BASED SYSTEMS, 2011, 19 (03) : 547 - 558
  • [37] Adapted random sampling patterns for accelerated MRI
    Florian Knoll
    Christian Clason
    Clemens Diwoky
    Rudolf Stollberger
    Magnetic Resonance Materials in Physics, Biology and Medicine, 2011, 24 : 43 - 50
  • [38] Using random sampling trees for automated planning
    Alcazar, Vidal
    Fernandez, Susana
    Borrajo, Daniel
    Veloso, Manuela
    AI COMMUNICATIONS, 2015, 28 (04) : 665 - 681
  • [39] RANDOM SAMPLING AND EFFICIENT ALGORITHMS FOR MULTISCALE PDEs
    Chen, Ke
    Li, Qin
    Lu, Jianfeng
    Wright, Stephen J.
    SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2020, 42 (05) : A2974 - A3005
  • [40] Adapted random sampling patterns for accelerated MRI
    Knoll, Florian
    Clason, Christian
    Diwoky, Clemens
    Stollberger, Rudolf
    MAGNETIC RESONANCE MATERIALS IN PHYSICS BIOLOGY AND MEDICINE, 2011, 24 (01) : 43 - 50
12345