Open access
Datum
2009Typ
- Report
ETH Bibliographie
yes
Altmetrics
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. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-a-005799190Publikationsstatus
publishedVerlag
ETH, Swiss Federal Institute of Technology Zürich, Computer Systems InstituteThema
GRAPHENALGORITHMEN + GEOMETRISCHE ALGORITHMEN (GRAPHENTHEORIE); PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; ZYKLEN (GRAPHENTHEORIE); HYPERGRAPHEN (GRAPHENTHEORIE); CYCLES (GRAPH THEORY); PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME; GRAPH ALGORITHMS + GEOMETRIC ALGORITHMS (GRAPH THEORY); HYPERGRAPHS (GRAPH THEORY)Organisationseinheit
02641 - Institut für Computersysteme (ehem.) / Computer Systems Institute (former)
Anmerkungen
Technical Reports D-INFK.ETH Bibliographie
yes
Altmetrics