Show simple item record

dc.contributor.author
Chebiryak, Yury
dc.contributor.author
Wahl, Thomas
dc.contributor.author
Haller, Leopold
dc.contributor.author
Kröning, Daniel
dc.date.accessioned
2017-11-07T09:54:28Z
dc.date.available
2017-06-10T18:28:59Z
dc.date.available
2017-11-07T09:54:28Z
dc.date.issued
2009
dc.identifier.uri
http://hdl.handle.net/20.500.11850/68636
dc.identifier.doi
10.3929/ethz-a-005799190
dc.description.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.
en_US
dc.format
application/pdf
dc.language.iso
en
en_US
dc.publisher
ETH, Swiss Federal Institute of Technology Zürich, Computer Systems Institute
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
GRAPHENALGORITHMEN + GEOMETRISCHE ALGORITHMEN (GRAPHENTHEORIE)
en_US
dc.subject
PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS
en_US
dc.subject
ZYKLEN (GRAPHENTHEORIE)
en_US
dc.subject
HYPERGRAPHEN (GRAPHENTHEORIE)
en_US
dc.subject
CYCLES (GRAPH THEORY)
en_US
dc.subject
PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME
en_US
dc.subject
GRAPH ALGORITHMS + GEOMETRIC ALGORITHMS (GRAPH THEORY)
en_US
dc.subject
HYPERGRAPHS (GRAPH THEORY)
en_US
dc.title
Finding lean induced cycles in binary hypercubes
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.size
14 p.
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.code.ddc
DDC - DDC::5 - Science::510 - Mathematics
en_US
ethz.code.ddc
DDC - DDC::5 - Science::510 - Mathematics
en_US
ethz.notes
Technical Reports D-INFK.
en_US
ethz.identifier.nebis
005799190
ethz.publication.place
Zürich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02641 - Institut für Computersysteme (ehem.) / Computer Systems Institute (former)
en_US
ethz.date.deposited
2017-06-10T18:30:48Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp59366ad33127c50384
ethz.identifier.importid
imp593650bc342c556970
ethz.ecolpid
eth:41761
ethz.ecitpid
pub:108979
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-26T16:31:17Z
ethz.rosetta.lastUpdated
2020-02-15T08:51:26Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Finding%20lean%20induced%20cycles%20in%20binary%20hypercubes&rft.date=2009&rft.au=Chebiryak,%20Yury&Wahl,%20Thomas&Haller,%20Leopold&Kr%C3%B6ning,%20Daniel&rft.genre=report&rft.btitle=Finding%20lean%20induced%20cycles%20in%20binary%20hypercubes
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record