Seminars in May 2012

  • Suil O (오수일), Path Cover Number in 4-regular Graphs and Hamiltonicity in Connected Regular Graphs
    Path Cover Number in 4-regular Graphs and Hamiltonicity in Connected Regular Graphs
    Suil O (오수일)
    Department of Mathematics, The College of William and Mary, Williamsburg, Virginia, USA
    2012/5/16 Wed 4PM
    A path cover of a graph is a set of disjoint paths such that every vertex in the graph appears in one of the paths. We prove an upper bound for the minimum size of a path cover in a connected 4-regular graph with n vertices, confirming a conjecture by Graffiti.pc. We also determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we solve the analogous problem for Hamiltonian paths.
    This is a partly joint work with Gexin Yu and Rui Xu.
    Tags:

  • Jeong-Han Kim (김정한), How to find counterfeit coins? An algorithmic version.
    How to find counterfeit coins? An algorithmic version.
    Jeong-Han Kim (김정한)
    Dept. of Mathematics, Yonsei University, Seoul, Korea.
    2012/05/03 Thu 4PM-5PM
    We consider a well-known combinatorial search problem. Suppose that there are n identical looking coins and some of them are counterfeit. The weights of all authentic coins are the same and known a priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing sets of coins (queries) on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins.
    We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most m≥2 and the weight w(c) of each counterfeit coin c satisfies α≤|w(c)|≤β for fixed constants α, β>0. The query complexity of the algorithm is O((m log n)/log m), which is optimal up to a constant factor. The algorithm uses, in part, random walks.
    We will also discuss the problem of finding edges of a hidden weighted graph using a certain type of queries.
    Tags:

Monthly Archives