Manuscripts


  1. Ho-Lin Chen, Peng-Ting Lin, and Meng-Tsung Tsai
    Streaming SCC Decomposition
    In submission.

Conference Papers


  1. Meng-Tsung Tsai, Shi-Chun Tsai, and Tsung-Ta Wu
    Dependent k-Set Packing on Polynomoids
    In: the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS), to appear. Dagstubl 2023


  2. Wing-Kai Hon, Meng-Tsung Tsai, and Hung-Lung Wang
    Verifying the Product of Generalized Boolean Matrix Multiplication and Its Applications to Detect Small Subgraphs
    In: the 18th International Symposium on Algorithms and Data Structures (WADS), to appear. Springer 2023


  3. Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai, and Hao-Tsung Yang
    Obtaining Approximately Optimal and Diverse Solutions via Dispersion
    In: the 15th Latin American Symposium on Theoretical Informatics (LATIN), pp. 222-239. Springer 2022


  4. Cheng-Hung Chiang and Meng-Tsung Tsai
    Single-Pass Streaming Algorithms to Partition Graphs into Few Forests
    In: the 27th International Conference on Computing and Combinatorics (COCOON), pp. 540-552. Springer 2021


  5. Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai
    Streaming Complexity of Spanning Tree Computation
    In: the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 30:1-30:19. Dagstubl 2020


  6. Eric Allender, Martín Farach-Colton, and Meng-Tsung Tsai
    Syntactic Separation of Subset Satisfiability Problems
    In: the 22th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 16:1-16:23. Dagstubl 2019


  7. Michael A. Bender, Jake Christensen, Alex Conway, Martín Farach-Colton, Rob Johnson, and Meng-Tsung Tsai
    Optimal Ball Recycling
    In: the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2527-2546. SIAM 2019


  8. Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai
    Streaming Algorithms for Planar Convex Hulls
    In: the 29th International Symposium on Algorithms and Computation (ISAAC), pp. 47:1-47:13. Dagstuhl 2018


  9. Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai
    A Dichotomy Result for Cyclic-Order Traversing Games
    In: the 29th International Symposium on Algorithms and Computation (ISAAC), pp. 29:1-29:13. Dagstuhl 2018


  10. Peyman Afshani, Michael A. Bender, Martín Farach-Colton, Jeremy Fineman, Mayank Goswami, and Meng-Tsung Tsai
    Cross-Referenced Dictionaries and the Limits of Write Optimization
    In: the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1523-1532. SIAM 2017


  11. Martín Farach-Colton and Meng-Tsung Tsai
    Tight Approximations of Graph Degeneracy in Large Graphs
    In: the 12th Latin American Symposium on Theoretical Informatics (LATIN), pp. 429-440. Springer 2016


  12. Martín Farach-Colton and Meng-Tsung Tsai
    On the Complexity of Computing Prime Tables
    In: the 26th International Symposium on Algorithms and Computation (ISAAC), pp. 677-688. Springer 2015


  13. Martín Farach-Colton, Tsan-sheng Hsu, Meng Li, and Meng-Tsung Tsai
    Finding Articulation Points of Large Graphs in Linear Time
    In: the 14th International Symposium on Algorithms and Data Structures (WADS), pp. 363-372. Springer 2015


  14. Michael A. Bender, Martín Farach-Colton, Mayank Goswami, Dzejla Medjedovic, Pablo Montes Arango, and Meng-Tsung Tsai
    The Batched Predecessor Problem in External Memory
    In: the 22nd European Symposium on Algorithms (ESA), pp. 112-124. Springer 2014


  15. Martín Farach-Colton and Meng-Tsung Tsai
    Computing the Degeneracy of Large Graphs
    In: the 11th Latin American Symposium on Theoretical Informatics (LATIN), pp. 250-260. Springer 2014


  16. Martín Farach-Colton and Meng-Tsung Tsai
    Exact Sublinear Binomial Sampling
    In: the 24th International Symposium on Algorithms and Computation (ISAAC), pp. 240-250. Springer 2013
    This paper is selected for a special issue of Algorithmica.


  17. Hung-Jui Chang, Meng-Tsung Tsai, and Tsan-sheng Hsu
    Game Tree Search with Adaptive Resolution
    In: the 13th International Conference on Advances in Computer Games (ACG), pp. 306-319. Springer 2011


  18. Meng-Tsung Tsai, Da-Wei Wang, Churn-Jung Liau, and Tsan-sheng Hsu
    Heterogeneous Subset Sampling
    In: the 16th International Conference on Computing and Combinatorics (COCOON), pp. 500-509. Springer 2010

Journal Papers


  1. Kuo-Kai Lee, Wing-Kai Hon, Chung-Shou Liao, Kunihiko Sadakane, Meng-Tsung Tsai
    Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries
    International Journal of Computational Geometry & Applications 33(1&2), pp. 43-54. World Scientific 2023


  2. Martín Farach-Colton and Meng-Tsung Tsai
    Exact Sublinear Binomial Sampling
    Algorithmica 73(4), pp. 637-651. Springer 2015


  3. Meng-Tsung Tsai, Tsurng-Chen Chern, Jen-Hsiang Chuang, Chih-Wen Hsueh, Hsu-Sung Kuo, Churn-Jung Liau, Steven Riley, Bing-Jie Shen, Chih-Hao Shen, Da-Wei Wang, and Tsan-Sheng Hsu
    Efficient Simulation of the Spatial Transmission Dynamics of Influenza
    PLoS ONE 5(11) 2010, p. e13292 11.