Counting Linear Extensions of Sparse Posets
Authors: Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, Mikko Koivisto
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate experimentally that these new algorithms outperform previously suggested ones for a wide range of posets, in particular when the posets are sparse. In Section 4 experimental results are presented to compare the two algorithms against previously known techniques. We have implemented all algorithmic techniques described in Sections 2 and 3 for experimental evaluation. |
| Researcher Affiliation | Academia | Kustaa Kangas Teemu Hankala Teppo Niinim aki Mikko Koivisto University of Helsinki, Department of Computer Science, Helsinki Institute for Information Technology HIIT, Finland {jwkangas,tjhankal,tzniinim,mkhkoivi}@cs.helsinki.fi |
| Pseudocode | No | The paper describes algorithms using text and mathematical notation, but does not include any explicitly labeled pseudocode blocks or algorithm figures. |
| Open Source Code | Yes | The program LEcount,1 comprising all implementations, was written in C++ and run on machines with Intel Xeon E5540 CPUs. Hashing was used in all implementations for storing the computed subproblems. All algorithms were given up to 20 minutes of CPU time and 30 GB of RAM on each poset. 1The LEcount program and all experiment posets are available at www.cs.helsinki.fi/u/jwkangas/lecount/. |
| Open Datasets | Yes | All posets used in these experiments were produced by randomly sampling directed acyclic graphs (DAGs) and taking for each DAG the corresponding partial order. 1The LEcount program and all experiment posets are available at www.cs.helsinki.fi/u/jwkangas/lecount/. |
| Dataset Splits | No | The paper describes the generation of posets used for experiments and compares algorithms on these generated posets. It does not mention any explicit training, validation, or test dataset splits. |
| Hardware Specification | Yes | The program LEcount... was written in C++ and run on machines with Intel Xeon E5540 CPUs. |
| Software Dependencies | No | The paper states that the program was |
| Experiment Setup | Yes | All algorithms were given up to 20 minutes of CPU time and 30 GB of RAM on each poset. |