×

Algorithmic combinatorics based on slicing posets. (English) Zbl 1100.05043

Digraphs have (quasi)-order ideals defined on them analogously to posets. Using the containment of sets order they generate distributive lattices. Using these lattices structures \(L\) may be modeled for which sublattices correspond to specialized substructures \(L_B\) themselves order ideals of digraphs obtained from the original digraphs by adding edges. Counting the order ideals of these derived digraphs provides the count of the set of specialized substructures. Examples of certain standard types of combinatorial problems of some generality and importance are provided. The edge adding can be accomplished in a mechanical and efficient method via an algorithm provided in this very useful paper.

MSC:

05C20 Directed graphs (digraphs), tournaments
05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices
05A17 Combinatorial aspects of partitions of integers
06D05 Structure and representation theory of distributive lattices
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Charron-Bost, B.; Delporte-Gallet, C.; Fauconnier, H., Local and temporal predicates in distributed systems, ACM Trans. Programming Languages Systems, 17, 1, 157-179 (1995)
[2] Cooper, R.; Marzullo, K., Consistent detection of global predicates, (Proc. Workshop on Parallel and Distributed Debugging, ACM/ONR. Proc. Workshop on Parallel and Distributed Debugging, ACM/ONR, Santa Cruz, CA (May 1991)), 163-173
[3] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (1990), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0701.06001
[4] S. Effler, F. Ruskey. A CAT algorithm for listing permutations with a given number of inversions, Inform. Process. Lett. 86 (2) (2003) 107-112.; S. Effler, F. Ruskey. A CAT algorithm for listing permutations with a given number of inversions, Inform. Process. Lett. 86 (2) (2003) 107-112. · Zbl 1173.68587
[5] Faigle, U.; Lovász, L.; Schrader, R.; Turán, Gy., Searching in trees, series-parallel and interval orders, SIAM J. Comput., 15, 4, 1075-1084 (1986) · Zbl 0619.68057
[6] Ferrari, L.; Rinaldi, S., Enumeration of generalized hook partitions, Integers Electron. J. Combinatorial Number Theory, 5, 1, A29 (2005) · Zbl 1134.11347
[7] Garg, V. K., Principles of Distributed Systems (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA
[8] Garg, V. K., Elements of Distributed Computing (2002), Wiley: Wiley New York, NY
[9] Garg, V. K., Enumerating global states of a distributed computation in lexicographic and breadth-first manner, (Internat. Conf. on Parallel and Distributed Computing and Systems (PDCS 2003) (2003)), 134-139
[10] Garg, V. K.; Mittal, N., On slicing a distributed computation, (21st Internat. Conf. on Distributed Computing Systems (ICDCS’ 01). 21st Internat. Conf. on Distributed Computing Systems (ICDCS’ 01), IEEE, Washington, Brussels, Tokyo (April 2001)), 322-329
[11] Jégou, R.; Medina, R.; Nourine, L., Linear space algorithm for on-line detection of global predicates, (Desel, J., Proc. Internat. Workshop on Structures in Concurrency Theory (STRICT), Workshops in Computing (1995), Springer: Springer Berlin), 175-189
[12] D.E. Knuth, Sorting and Searching, The Art of Computer Programming, second ed., Vol. 3, Addison-Wesley, Reading, MA, USA, 1998.; D.E. Knuth, Sorting and Searching, The Art of Computer Programming, second ed., Vol. 3, Addison-Wesley, Reading, MA, USA, 1998. · Zbl 0883.68015
[13] Mittal, N.; Garg, V. K., Slicing a distributed computation: techniques and theory, (Fifth Internat. Symp. on DIStributed Computing (DISC’01) (13 October 2001)), 78-92 · Zbl 1024.68518
[14] Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 777-788 (1983) · Zbl 0524.68041
[15] Spinrad, J., On comparability and permutation graphs, SIAM J. Comput., 14, 3, 658-670 (1985) · Zbl 0568.68051
[16] M. Squire, Gray codes and efficient generation of combinatorial structures, Ph.D. Dissertation, Department of Computer Science, North Carolina State University, 1995.; M. Squire, Gray codes and efficient generation of combinatorial structures, Ph.D. Dissertation, Department of Computer Science, North Carolina State University, 1995.
[17] R. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brookes/Cole, Monterey, California, 1986.; R. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brookes/Cole, Monterey, California, 1986. · Zbl 0608.05001
[18] Stanton, D.; White, D., Constructive Combinatorics (1986), Springer: Springer Berlin · Zbl 0595.05002
[19] Steiner, G., Single machine scheduling with precedence constraints of dimension 2, Math. Oper. Res., 9, 248-259 (1984) · Zbl 0541.90054
[20] Steiner, G., An algorithm to generate the ideals of a partial order, Oper. Res. Lett., 5, 6, 317-320 (1986) · Zbl 0608.90075
[21] Trotter, W. T., Combinatorics and Partially Ordered Sets: Dimension Theory (1992), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0764.05001
[22] van Lint, J. H.; Wilson, R. M., A Course in Combinatorics (1992), Cambridge University Press: Cambridge University Press Cambridge, MA · Zbl 0769.05001
[23] Venkatesan, S.; Dathan, B., Techniques to tackle state explosion in global predicate detection, IEEE Trans. Software Eng., 27, 8, 704-714 (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.