Abstract
Covering subsequences by sets of permutations arises in numerous applications. Given a set of permutations that cover a specific set of subsequences, it is of interest not just to know how few permutations can be used, but also to find a set of size equal to or close to the minimum. These permutation construction problems have proved to be computationally challenging; few explicit constructions have been found for small sets of permutations of intermediate length, mostly arising from greedy algorithms. A different strategy is developed here. Starting with a set that covers the specific subsequences required, we determine local changes that can be made in the permutations without losing the required coverage. By selecting these local changes (using linear extensions) so as to make one or more permutations less ‘important’ for coverage, the method attempts to make a permutation redundant so that it can be removed and the set size reduced. A post-optimization method to do this is developed, and preliminary results on sequence covering arrays show that it is surprisingly effective.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Banbara, M., Tamura, N., Inoue, K.: Generating event-sequence test cases by answer set programming with the incidence matrix. In: Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012), pp. 86–97 (2012)
Basavaraju, M., Chandran, L.S., Golumbic, M.C., Mathew, R., Rajendraprasad, D.: Boxicity and separation dimension. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 81–92. Springer, Heidelberg (2014)
Brain, M., Erdem, E., Inoue, K., Oetsch, J., Pührer, J., Tompits, H., Yilmaz, C.: Event-sequence testing using answer-set programming. Int. J. Adv. Softw. 5(3–4), 237–251 (2012)
Brightwell, G., Winkler, P.: Counting linear extensions. Order 8(3), 225–242 (1991)
Chee, Y.M., Colbourn, C.J., Horsley, D., Zhou, J.: Sequence covering arrays. SIAM J. Discrete Math. 27(4), 1844–1861 (2013)
Chor, B., Sudan, M.: A geometric approach to betweenness. SIAM J. Discrete Math. 11(4), 511–523 (1998)
Colbourn, C.J., Nayeri, P.: Randomized Post-optimization for t-Restrictions. In: Aydinian, H., Cicalese, F., Deppe, C. (eds.) Ahlswede Festschrift. LNCS, vol. 7777, pp. 597–608. Springer, Heidelberg (2013)
Dushnik, B.: Concerning a certain set of arrangements. Proc. Amer. Math. Soc. 1, 788–796 (1950)
Erdem, E., Inoue, K., Oetsch, J., Pührer, J., Tompits, H., Yilmaz, C.: Answer-set programming as a new approach to event-sequence testing. In: Proceedings of the Second International Conference on Advances in System Testing and Validation Lifecycle, pp. 25–34. Xpert Publishing Services (2011)
Fishburn, P.C., Trotter, W.T.: Dimensions of hypergraphs. J. Combin. Theory Ser. B 56(2), 278–295 (1992)
Füredi, Z.: Scrambling permutations and entropy of hypergraphs. Random Struct. Alg. 8(2), 97–104 (1996)
Hazli, M.M.Z., Zamli, K.Z., Othman, R.R.: Sequence-based interaction testing implementation using bees algorithm. In: 2012 IEEE Symposium on Computers and Informatics, pp. 81–85. IEEE (2012)
Huber, M.: Fast perfect sampling from linear extensions. Discrete Math. 306(4), 420–428 (2006)
Ishigami, Y.: Containment problems in high-dimensional spaces. Graphs Combin. 11(4), 327–335 (1995)
Ishigami, Y.: An extremal problem of \(d\) permutations containing every permutation of every \(t\) elements. Discrete Math. 159(1–3), 279–283 (1996)
Karzanov, A., Khachiyan, L.: On the conductance of order Markov chains. Order 8(1), 7–15 (1991)
Kuhn, D.R., Higdon, J.M., Lawrence, J.F., Kacker, R.N., Lei, Y.: Combinatorial methods for event sequence testing. CrossTalk: J. Defense Software Eng. 25(4), 15–18 (2012)
Kuhn, D.R., Higdon, J.M., Lawrence, J.F., Kacker, R.N., Lei, Y.: Combinatorial methods for event sequence testing. In: IEEE Fifth International Conference on Software Testing, Verification and Validation (ICST), pp. 601–609 (2012)
Levenshteĭn, V.I.: Perfect codes in the metric of deletions and insertions. Diskret. Mat. 3(1), 3–20 (1991)
Margalit, O.: Better bounds for event sequence testing. In: The 2nd International Workshop on Combinatorial Testing (IWCT 2013), pp. 281–284 (2013)
Mathon, R.: Tran Van Trung: Directed \(t\)-packings and directed \(t\)-Steiner systems. Des. Codes Cryptogr. 18(1–3), 187–198 (1999)
Nayeri, P., Colbourn, C.J., Konjevod, G.: Randomized postoptimization of covering arrays. Eur. J. Comb. 34, 91–103 (2013)
Opatrný, J.: Total ordering problem. SIAM J. Comput. 8(1), 111–114 (1979)
Radhakrishnan, J.: A note on scrambling permutations. Random Struct. Alg. 22(4), 435–439 (2003)
Spencer, J.: Minimal scrambling sets of simple orders. Acta Math. Acad. Sci. Hungar. 22, 349–353 (1971/72)
Tarui, J.: On the minimum number of completely 3-scrambling permutations. Discrete Math. 308(8), 1350–1354 (2008)
Acknowledgments
Thanks to Sunil Chandran, Marty Golumbic, Rogers Mathew, and Deepak Rajendraprasad for interesting discussions about permutation coverings and geometric representations of graphs and hypergraphs.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Murray, P.C., Colbourn, C.J. (2015). Sequence Covering Arrays and Linear Extensions. In: Jan, K., Miller, M., Froncek, D. (eds) Combinatorial Algorithms. IWOCA 2014. Lecture Notes in Computer Science(), vol 8986. Springer, Cham. https://doi.org/10.1007/978-3-319-19315-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-19315-1_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19314-4
Online ISBN: 978-3-319-19315-1
eBook Packages: Computer ScienceComputer Science (R0)