Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Irit Katriel"'
Publikováno v:
Journal of Computer and System Sciences. 74:884-897
Given a bipartite graph G=([email protected][email protected]?D,[email protected]?XxD), an X-perfect matching is a matching in G that covers every node in X. In this paper we study the following generalisation of the X-perfect matching problem, which
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::209c26e4fda4baa324da453d67cf70ff
https://doi.org/10.1016/j.jcss.2008.02.001
https://doi.org/10.1016/j.jcss.2008.02.001
Autor:
Irit Katriel
Publikováno v:
INFORMS Journal on Computing. 20:205-211
Matchings in convex bipartite graphs correspond to the problem of scheduling unit-length tasks on a single disjunctive resource, given a release time and a deadline for every task. The unweighted case was studied by several authors since Glover first
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f0ea58b60e9514e2858fb5c911890bc2
https://doi.org/10.1287/ijoc.1070.0232
https://doi.org/10.1287/ijoc.1070.0232
Publikováno v:
Operations Research Letters. 36:14-18
We show that the minmax regret median of a tree can be found in O(nlogn) time. This is obtained by a modification of Averbakh and Berman's O(nlog^2n)-time algorithm: we design a dynamic solution to their bottleneck subproblem of finding the middle of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6c4517d5941df550866cee55a50f7434
https://doi.org/10.1016/j.orl.2007.02.012
https://doi.org/10.1016/j.orl.2007.02.012
Autor:
Irit Katriel, Alon Itai
Publikováno v:
Information Processing Letters. 104:200-204
The Sparse Table is a data structure for controlling density in an array which was first proposed in 1981 and has recently reappeared as a component of cache-oblivious data structures. All existing variants of the Sparse Table divide the array into b
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::da9d4f6439926354516733e14ef50016
https://doi.org/10.1016/j.ipl.2007.07.001
https://doi.org/10.1016/j.ipl.2007.07.001
Autor:
Khaled Elbassioni, Irit Katriel
Publikováno v:
Khaled, E & Katriel, I 2006, ' Multiconsistency and Robustness with Global Constraints ', Constraints, vol. 11, no. 4, pp. 335-352 .
We propose a natural generalization of arc-consistency, which we call multiconsistency: a value v in the domain of a variable x is k-multiconsistent with respect to a constraint C if there are at least k solutions to C in which x is assigned the valu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::26c831cd6c7de649c5efdd622ff3d374
https://doi.org/10.1007/s10601-006-9004-6
https://doi.org/10.1007/s10601-006-9004-6
Autor:
Hans L. Bodlaender, Irit Katriel
Publikováno v:
Katriel, I & Bodlaender, H L 2006, ' Online Topological Ordering ', A C M Transactions on Algorithms, vol. 2, no. 3, pp. 364-379 .
It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O (min{ m 3/2 log n , m 3/2 + n 2 log n }) time, an improvement over the best known result of O ( mn )
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8c4a5ec9647567f556881dcbadec0dfb
https://doi.org/10.1145/1159892.1159896
https://doi.org/10.1145/1159892.1159896
Autor:
Sven Thiel, Irit Katriel
Publikováno v:
Constraints. 10:191-217
We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n + n?) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n? is the number
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1b13f6afcde1ff1aacb4d11e07112d9d
https://doi.org/10.1007/s10601-005-2237-y
https://doi.org/10.1007/s10601-005-2237-y
Publikováno v:
CP
Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acy
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::772c8fab9f6a73969c99e163618e86b4
https://doi.org/10.1007/s10601-005-0554-9
https://doi.org/10.1007/s10601-005-0554-9
Autor:
Irit Katriel
Publikováno v:
Information Processing Letters. 92:175-178
We present a linear-time algorithm in the algebraic computation tree model for checking whether two sets of integers are equal. The significance of this result is in the fact that it shows that set equality testing is computationally easier when the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c1545016403a5bbd9dc6862dacfa122a
https://doi.org/10.1016/j.ipl.2004.07.006
https://doi.org/10.1016/j.ipl.2004.07.006
Publikováno v:
Automata, Languages and Programming ISBN: 9783540734192
ICALP
ICALP
We define and study two versions of the bipartite matching problem in the framework of two-stage stochastic optimization with recourse. In one version the uncertainty is in the second stage costs of the edges, in the other version the uncertainty is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9c198e9a07e9202feb762d088bd27dbb
https://doi.org/10.1007/978-3-540-73420-8_17
https://doi.org/10.1007/978-3-540-73420-8_17
