We present a matrix permutation algorithm for computing a minimal vertex cover from a maximal matching in a bipartite graph. Our algorithm is linear time and linear space, and provides an interesting perspective on a well known problem. Unlike most algorithms, it does not use the concept of alternating paths, and it is formulated entirely in terms of combinatorial operations on a binary matrix. The algorithm relies on permutations of rows and columns of a 0-1 matrix which encodes a bipartite graph together with its maximal matching. This problem has many important applications such as network switches which essentially compute maximal matchings between their incoming and outgoing ports.
A new paper: On normalization of inconsistency indicators in pairwise comparisons, by W.W. Koczkodaj, J.-P. Magnot, J. Mazurek, J.F. Peters, H. Rakhshani, M. Soltys, D. Strzałka, J. Szybowski and A. Tozzi.
Abstract: In this study, we provide mathematical and practice-driven justification for using [0,1] normalization of inconsistency indicators in pairwise comparisons. The need for normalization, as well as problems with the lack of normalization, are presented. A new type of paradox of infinity is described.
The paper can be found here: https://arxiv.org/abs/1702.07205v2
Title: Non-repetitive strings over alphabet lists
Authors: Neerja Mhaskar and Michael Soltys
Abstract: A word is non-repetitive if it does not contain a subword of the form vv. Given a list of alphabets L = L1, L2, . . . , Ln, we investigate the question of generating non-repetitive words w = w1w2 . . . wn, such that the symbol wi is a letter in the alphabet Li. This problem has been studied by several authors (e.g., [GKM10], [Sha09]), and it is a natural extension of the original problem posed and solved by A. Thue. While we do not solve the problem in its full generality, we show that such strings exist over many classes of lists. We also suggest techniques for tackling the problem, ranging from online algorithms, to combinatorics over 0-1 matrices, and to proof complexity. Finally, we show some properties of the extension of the problem to abelian squares.
Title: String Shuffle: Circuits and Graphs
Authors: Neerja Mhaskar and Michael Soltys
Abstract: We show that shuffle, the problem of determining whether a string w can be composed from an order preserving shuffle of strings x and y, is not in AC0, but it is in AC1. The fact that shuffle is not in AC0 is shown by a reduction of parity to shuffle and invoking the seminal result of Furst et al., while the fact that it is in AC1 is implicit in the results of Mansfield. Together, the two results provide a lower and upper bound on the complexity of this combinatorial problem. We also explore an interesting relationship between graphs and the shuffle problem, namely what types of graphs can be represented with strings exhibiting the anti-Monge condition.
The CSU Trustees’ Award for Outstanding Achievement Scholarship is available for the 2015-2016 academic year. Students who have overcome adversity, demonstrated financial need, and have attributes of merit, including significant personal achievements, superior academic performance, and exemplary community service are eligible for this award.
The CSU Trustees Award will be available for STEM (Science, Technology, Engineering and Math) students, an Information Technology student, engineers, a veteran, a student who gives the most to his/her home, university, or global community, students studying the humanities, and students studying to become teachers.
Scholarships will be awarded in the amount of $6,000 for the 2015-2016 academic year.
- Demonstrate superior academic performance with a minimum cumulative GPA of 3.0 on a 4.0 scale and be in good academic standing.
- Demonstrate financial need as determined by the campus Financial Aid and Scholarships office.
- Be currently enrolled as a full-time equivalent undergrad or graduate student in any major field at a CSU campus and remain a CSU full-time equivalent student during the upcoming academic year.
Application Deadline: Friday, April 3, 2015
For detailed information regarding this scholarship including the application and selection process, please contact Jose Delgado, Scholarship Coordinator directly at (805) 437-8499 or firstname.lastname@example.org.
The National Engineer’s Week Committee of Ventura and Santa Barbara Counties will award a limited number of scholarships, based on the availability of funds, to academically meritorious or needy students. If your grades are good (GPA 3.0 or better), you should apply! We evaluate every application on the merits and background of the individual. The scholarships may range from $500-$1,500.
Check here for details: http://www.newc-vsb.org