Open access
Date
2009Type
- Report
ETH Bibliography
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. Show more
Permanent link
https://doi.org/10.3929/ethz-a-005799190Publication status
publishedPublisher
ETH, Swiss Federal Institute of Technology Zürich, Computer Systems InstituteSubject
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)Organisational unit
02641 - Institut für Computersysteme (ehem.) / Computer Systems Institute (former)
Notes
Technical Reports D-INFK.More
Show all metadata
ETH Bibliography
yes
Altmetrics