STShen-Fu Tsai
Shen-Fu Tsai
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Shen-Fu Tsai has a total of 16 co-authors. Here are the top co-authors by number of shared publications:
- Jesse Geneson
Department of Mathematics Iowa State University 50011 Ames IA USA
3 shared publications - Carolyn Reinhart
Department of Mathematics and Statistics Swarthmore College Swarthmore PA USA
2 shared publications Jesse Geneson
2 shared publicationsAnand
Univ British Columbia, Vancouver, BC, Canada
1 shared publication- Boris Brimkov
Department of Mathematics, Statistics, and Physics Slippery Rock University
1 shared publication - Boris Brimkov
Slippery Rock University, USA
1 shared publication
Latest Publications
- 5 October 2026
- Published by Elsevier in Linear Algebra and its Applications
Pattern forcing (0,1)-matrices
- 5 October 2026
- Published by Elsevier in Linear Algebra and its Applications
Pattern forcing (0,1)-matrices
- 21 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Throttling for metric dimension and its variants
- 21 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1073
Throttling for metric dimension and its variants
- Open Access
Throttling for metric dimension and its variants
Metric dimension is a graph parameter that has been applied to robot navigation and finding low-dimensional vector embeddings. Throttling entails minimizing the sum of two available resources when solving certain graph problems. In this paper, we introduce throttling for metric dimension, edge metric dimension, and mixed metric dimension. In the context of vector embeddings, metric dimension throttling finds a low-dimensional, low-magnitude embedding with integer coordinates. We show that computing the throttling number is NP-hard for all three variants. We give formulas for the throttling numbers of special families of graphs, and characterize graphs with extremal throttling numbers. We also prove that the minimum possible throttling number of a graph of order $n$ is $Θ\left(\frac{\log{n}}{\log{\log{n}}}\right)$, while the minimum possible throttling number of a tree of order $n$ is $Θ(n^{1/3})$ or $Θ(n^{1/2})$ depending on the variant of metric dimension.Open AccessThrottling for metric dimension and its variants
Metric dimension is a graph parameter that has been applied to robot navigation and finding low-dimensional vector embeddings. Throttling entails minimizing the sum of two available resources when solving certain graph problems. In this paper, we introduce throttling for metric dimension, edge metric dimension, and mixed metric dimension. In the context of vector embeddings, metric dimension throttling finds a low-dimensional, low-magnitude embedding with integer coordinates. We show that computing the throttling number is NP-hard for all three variants. We give formulas for the throttling numbers of special families of graphs, and characterize graphs with extremal throttling numbers. We also prove that the minimum possible throttling number of a graph of order $n$ is $Θ\left(\frac{\log{n}}{\log{\log{n}}}\right)$, while the minimum possible throttling number of a tree of order $n$ is $Θ(n^{1/3})$ or $Θ(n^{1/2})$ depending on the variant of metric dimension. - 31 October 2024
- Published by Elsevier in Discrete Mathematics
- Vol. 348 (2)
Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
- 31 October 2024
- Published by Elsevier in Discrete Mathematics
- Vol. 348 (2)
Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
- 9 October 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 360, 382-393
Sequence saturation
- 9 October 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 360, 382-393
Sequence saturation
- Open Access
Two properties of maximal antichains in strict chain product posets
We present two results on maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\ldots\times[t_n+1]$. First, we prove that these maximal antichains are also maximum. Second, we prove that there is a bijection between maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\ldots\times[t_n+1]$ and antichains in the non-strict chain product poset $[t_1]\times[t_2]\times\ldots\times[t_n]$.Open AccessTwo properties of maximal antichains in strict chain product posets
We present two results on maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\ldots\times[t_n+1]$. First, we prove that these maximal antichains are also maximum. Second, we prove that there is a bijection between maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\ldots\times[t_n+1]$ and antichains in the non-strict chain product poset $[t_1]\times[t_2]\times\ldots\times[t_n]$. - Open Access
- 22 December 2020
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 15 (3) , 130-132
Two properties of maximal antichains in strict chain product posets
We present two results on maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\cdots\times[t_n+1]$. First, we prove that these maximal antichains are also maximum. Second, we prove that there is a bijection between maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\cdots\times[t_n+1]$ and antichains in the nonstrict chain product poset $[t_1]\times[t_2]\times\cdots\times[t_n]$.- 22 December 2020
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 15 (3) , 130-132
Open AccessTwo properties of maximal antichains in strict chain product posets
We present two results on maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\cdots\times[t_n+1]$. First, we prove that these maximal antichains are also maximum. Second, we prove that there is a bijection between maximal antichains in the strict chain product poset $[t_1+1]\times[t_2+1]\times\cdots\times[t_n+1]$ and antichains in the nonstrict chain product poset $[t_1]\times[t_2]\times\cdots\times[t_n]$. - Open Access
Expected capture time and throttling number for cop versus gambler
We bound expected capture time and throttling number for the cop versus gambler game on a connected graph with $n$ vertices, a variant of the cop versus robber game that is played in darkness, where the adversary hops between vertices using a fixed probability distribution. The paper that originally defined the cop versus gambler game focused on two versions, a known gambler whose distribution the cop knows, and an unknown gambler whose distribution is secret. We define a new version of the gambler where the cop makes a fixed number of observations before the lights go out and the game begins. We show that the strategy that gives the best possible expected capture time of $n$ for the known gambler can also be used to achieve nearly the same expected capture time against the observed gambler when the cop makes a sufficiently large number of observations. We also show that even with only a single observation, the cop is able to achieve an expected capture time of approximately $1.5n$, which is much lower than the expected capture time of the best known strategy against the unknown gambler (approximately $1.95n$).Open AccessExpected capture time and throttling number for cop versus gambler
We bound expected capture time and throttling number for the cop versus gambler game on a connected graph with $n$ vertices, a variant of the cop versus robber game that is played in darkness, where the adversary hops between vertices using a fixed probability distribution. The paper that originally defined the cop versus gambler game focused on two versions, a known gambler whose distribution the cop knows, and an unknown gambler whose distribution is secret. We define a new version of the gambler where the cop makes a fixed number of observations before the lights go out and the game begins. We show that the strategy that gives the best possible expected capture time of $n$ for the known gambler can also be used to achieve nearly the same expected capture time against the observed gambler when the cop makes a sufficiently large number of observations. We also show that even with only a single observation, the cop is able to achieve an expected capture time of approximately $1.5n$, which is much lower than the expected capture time of the best known strategy against the unknown gambler (approximately $1.95n$). - 4 December 2018
- Published by Springer Nature in Order
- Vol. 36 (3) , 507-510
A Simple Upper Bound on the Number of Antichains in [t]n
- 4 December 2018
- Published by Springer Nature in Order
- Vol. 36 (3) , 507-510
A Simple Upper Bound on the Number of Antichains in [t]n
- Open Access
Computing optimal strategy for cop in the game of Cop v.s. Gambler
We present two efficient algorithms that compute the optimal strategy for cop in the game of Cop v.s. Gambler where the gambler's strategy is not optimal but known to the cop. The first algorithm is analogous to Bellman-Ford algorithm for single source shortest path problem and runs in $O(|V(G)||E(G)|)$ time. The second is analogous to Dijkstra's algorithm and runs in $O(|E(G)|+|V(G)|\log |V(G)|)$ time. Compared with each other, they are more suitable for sparse and dense graphs, respectively.Open AccessComputing optimal strategy for cop in the game of Cop v.s. Gambler
We present two efficient algorithms that compute the optimal strategy for cop in the game of Cop v.s. Gambler where the gambler's strategy is not optimal but known to the cop. The first algorithm is analogous to Bellman-Ford algorithm for single source shortest path problem and runs in $O(|V(G)||E(G)|)$ time. The second is analogous to Dijkstra's algorithm and runs in $O(|E(G)|+|V(G)|\log |V(G)|)$ time. Compared with each other, they are more suitable for sparse and dense graphs, respectively.