Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Artículo Open Access |
| Veröffentlicht: |
Wiley
2025
|
| Schlagworte: | |
| Online-Zugang: | https://onlinelibrary.wiley.com/doi/10.1002/jcd.21990 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- A Note on Finding Large Transversals Efficiently Michael Anastos Patrick Morris Journal of Combinatorial Designs ABSTRACTIn an array filled with symbols, a transversal is a collection of entries with distinct rows, columns and symbols. In this note we show that if no symbol appears more than times, the array contains a transversal of size . In particular, if the array is filled with symbols, each appearing times (an equi‐ square), we get transversals of size . Moreover, our proof gives a deterministic algorithm with polynomial running time, that finds these transversals. 10.1002/jcd.21990 http://onlinelibrary.wiley.com/termsAndConditions#vor