Zobrazeno 1 - 10
of 31
pro vyhledávání: '"Stefan Porschen"'
Autor:
Stefan Porschen
Publikováno v:
IAENG Transactions on Engineering Sciences.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::af232369056fa878422c5829a5d62312
https://doi.org/10.1142/9789813142725_0019
https://doi.org/10.1142/9789813142725_0019
Autor:
Stefan Porschen
Publikováno v:
International Journal of Computational Geometry & Applications. 19:325-340
Many applications like image processing, data compression or pattern recognition require a covering of a set of n points most often located in the (discrete) plane by rectangles due to specific cost constraints. In this paper we provide exact dynamic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b818b6288c6e5fdc922482125a54a56a
https://doi.org/10.1142/s0218195909002988
https://doi.org/10.1142/s0218195909002988
Autor:
Stefan Porschen, Ewald Speckenmeyer
Publikováno v:
Discrete Applied Mathematics. 155(11):1408-1419
In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be enc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4b700accd44bf373787858a9d3b4cc2b
Publikováno v:
Annals of Mathematics and Artificial Intelligence. 43:173-193
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4167c1e98e7380b90487741c6dd4a744
https://doi.org/10.1007/s10472-005-0428-2
https://doi.org/10.1007/s10472-005-0428-2
Publikováno v:
Journal of Computer and System Sciences. 67(4):772-788
Consider a forest of k trees and n nodes together with a (partial) function σ mapping leaves of the trees to non-root nodes of other trees. Define the shadow of a leaf ℓ to be the subtree rooted at σ(ℓ). The shadow problem asks whether there is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::abb306bce2073b51ffee9c3c3a213ed3
Autor:
Stefan Porschen
Publikováno v:
Electronic Notes in Discrete Mathematics. 8:80-83
A problem of combinatorial geometry is discussed: Cover a finite set of points lying on an integer grid in the Euclidean plane by regular rectangles such that the total area, circumference and number of rectangles used is minimized. This problem seem
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d3e8a10f1010e5a6592fc3bb2e6e8c2b
https://doi.org/10.1016/s1571-0653(05)80086-1
https://doi.org/10.1016/s1571-0653(05)80086-1
Autor:
Stefan Porschen
Publikováno v:
Lecture Notes in Electrical Engineering ISBN: 9781461416944
We consider a specific class of combinatorial search respectively optimization problems where the search space gives rise to a closure operator and essentially the hulls are the only relevant subsets that must be checked in a brute force approach. We
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::687fef737bab09e2280403772542ce8d
https://doi.org/10.1007/978-1-4614-1695-1_25
https://doi.org/10.1007/978-1-4614-1695-1_25
Publikováno v:
Theory and Applications of Satisfiability Testing-SAT 2011 ISBN: 9783642215803
SAT
SAT
A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in computational biology to compare evolutionary histories of species. In this paper we present a formulati
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c9bd7d33ef7989e184c37723bfed690a
https://kups.ub.uni-koeln.de/55007/
https://kups.ub.uni-koeln.de/55007/
XSAT and NAE-SAT are important variants of the propositional satisfiability problem (SAT). XSAT contains all CNF formulas that can be satisfied by setting exactly one literal in each clause to 1, whereas NAE-SAT requires satisfying truth assignments
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::adfd0046ced4d9c42cefe356c21c8cda
https://kups.ub.uni-koeln.de/55020/
https://kups.ub.uni-koeln.de/55020/
Publikováno v:
Theory and Applications of Satisfiability Testing – SAT 2010 ISBN: 9783642141850
SAT
SAT
We investigate the computational complexity of the exact satisfiability problem (XSAT) restricted to certain subclasses of linear CNF formulas. These classes are defined through restricting the number of occurrences of variables and are therefore int
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6d633c4cff6e137471b35644dfbb3d42
https://doi.org/10.1007/978-3-642-14186-7_21
https://doi.org/10.1007/978-3-642-14186-7_21