Name
Abstract | ||
|---|---|---|
Induced (chord-free) cycles in binary hypercubes have many applications in computer science. The state of the art for computing such cycles relies on genetic algorithms, which are, however, unable to perform a complete search. In this paper, we propose an approach to finding a special class of induced cycles we call lean , based on an efficient propositional SAT encoding. Lean induced cycles dominate a minimum number of hypercube nodes. Such cycles have been identified in Systems Biology as candidates for stable trajectories of gene regulatory networks. The encoding enabled us to compute lean induced cycles for hypercubes up to dimension 7. We also classify the induced cycles by the number of nodes they fail to dominate, using a custom-built All-SAT solver. We demonstrate how clause filtering can reduce the number of blocking clauses by two orders of magnitude. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02777-2_4 | SAT |
Keywords | Field | DocType |
complete search,sat encoding,lean induced cycle,custom-built all-sat solver,finding lean induced cycles,binary hypercubes,efficient propositional,systems biology,minimum number,computer science,induced cycle,gene regulatory network,system biology,genetic algorithm,sat solver | Discrete mathematics,Combinatorics,Computer science,Algorithm,Filter (signal processing),Solver,Gene regulatory network,Genetic algorithm,Hypercube,Encoding (memory),Binary number | Conference |
Volume | ISSN | Citations |
5584 | 0302-9743 | 1 |
PageRank | References | Authors |
0.36 | 17 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yury Chebiryak | 1 | 20 | 2.19 |
| Thomas Wahl | 2 | 103 | 10.21 |
| Daniel Kroening | 3 | 3084 | 187.60 |
| Leopold Haller | 4 | 127 | 6.93 |