Optimal Deterministic Algorithm for the Hammock(2,2)-Poset Cover Problem
Ivy D. Ordanel* and Henry N. Adorna
Department of Computer Science, University of the Philippines Diliman, Quezon City, Philippines
*Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.
ABSTRACT
INTRODUCTION
Consider the ordering of different tasks in Figure 1. Suppose a teacher gives those tasks to students and the students need to finish all of them. From the graph, there are some tasks that are dependent on other tasks. For example, Tasks 2, 3, and 4 need to be accomplished first before proceeding on Task 5. There are also some tasks that do not have dependencies. For example, Task 6 is not dependent on Task 7, so it does not matter which one between them will be started first. With this ordering, one student can do all the tasks in the following order: Task 1 →Task 2 → Task 3 → Task 4 → Task 5 → Task 6 → Task 7 → Task 8. Another student can accomplish all the task as follows: Task 1→ Task 3 → Task 2 → Task 4 → Task 5 → Task 7 → Task 6 → Task 8. There are actually 12 possible ways on which a student can finish all the tasks. This is a typical scenario – an ordering is given and the flow of events . . . . read more
REFERENCES
AGRAWAL R, GUNOPULOS D, LEYMANN F. 1998. Mining process models from workflow logs. Springer Berlin Heidelberg.
ARKIN A, SHENG P, ROSS J. 1997. A test case of correlation metric construction of a reaction pathway from measurements. Science 277: 1275–79.
BLÄSER M, MANTHEY B. 2002. Two approximation algorithms for 3-cycle covers. Berlin, Heidelberg: Springer.
CHASE PJ. 1973. Transposition Graphs. SIAM Journal on Computing 2(2): 128–133.
DER AALST WV, WEIJTERS T, MARUSTER L. 2004. Workflow mining: Discovering process models from event logs. Knowledge and Data Engineering, IEEE Transactions 16(9): 1128–42.
FERNANDEZ PL, HEATH LS, RAMAKRISHNAN N, TAN M, VERGARA JP. 2013. Mining Posets from Linear Orders. Discrete Mathematics, Algorithms and Applications 5(4).
GAREY M, JOHNSON D. 1979. A Guide to the Theory of NP-Completeness. New York: WH Freemann.
HEATH LS, NEMA AK. 2013. The Poset Cover Problem. Open Journal of Discrete Mathematics 3(03): 101–111.
LEE A, WILSON M. 2005. A Combinatorial Method for Analyzing Sequential Firing Patterns Involving an Arbitrary Number of Neurons Based on Relative Time Order. Journal of Neurophysiology 92(4): 2555–73.
MANNILA H. 2008. Finding Total and Partial Orders from Data for Seriation. In: International Conference on Discovery Science. Berlin, Heidelberg: Springer. p. 16–25.
NORMAN R, RABIN M. 1959. An algorithm for a minimum cover of a graph. Proceedings of the American Mathematical Society 10(2): 315–319.
ORDANEL I, ADORNA H. 2017. Two Approximation Algorithms to the Poset Cover Problem. Proceedings of the 17th Philippine Computing Science Congress. p. 179–184.
ORDANEL I, FERNANDEZ P. 2011. Reconstructing a Tree Poset from Linear Extensions. Philippine Information Technology Journal 4: 18–23.
ORDANEL I, ADORNA H, CLEMENTE J. 2017. Approximation of two simple variations of the Poset Cover Problem. Workshop on Computation: Theory and Practice (WCTP 2017), 12–13 Sep 2017, Osaka University Nakanoshima Center, Osaka, Japan.
PETERSON PA, LOUI M. 1988. The general maximum matching algorithm of Micali and Vazirani. Algorithmica 3(1–4): 511–533.
PUOLAMÄKI K, FORTELIUS M, MANNILA H. 2006. Seriation in Paleontological Data: Using Markov Chain Monte Carlo Methods. PLoS Computational Biology 2(2).
SANCHEZ GA, FERNANDEZ P, VERGARA JP. 2014. Some Heuristics for the 2-Poset Cover Problem. Philippine Computing Journal 9: 26–32.
UNNIKRISHNAN KP, RAMAKRISHNAN N, SASTRY PS, UTHURUSAMY R. 2006. Network reconstruction from dynamic data. ACM SIGKDD Exploration Newsletter 8(2): 90–91.
UNO T. 1997. Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. International Symposium on Algorithms and Computation. Berlin, Heidelberg: Springer. p. 92–101.
VALIANT LG. 1979. The complexity of enumeration and reliability problems. SIAM Journal on Computing 8(3): 410–421.
WIGGINS C, NEMENMAN I. 2003. Process Pathway via Time Series Analysis. Experimental Mechanics 43(3): 361–370.
