Bounded Incremental Single-Source Shortest-Paths (2008)
Irit Katriel, Pascal Van Hentenryck
Abstract. We consider the problem of maintaining the distances of all vertices of a directed graph from a specific vertex, its source. We show algorithms in the bounded incremental computation (BIC)...
Graph Constraints in Constraint Programming: Weighted Spanning Trees (2008)
Abstract. The recently introduced CP(Graph) framework consists of a constraint solver that allows the programmer to declare variables whose values are graphs and to specify properties that these...
Abstract Simultaneous Matchings: Hardness and Approximation ⋆ (2008)
Martin Kutz, Khaled Elbassioni, Irit Katriel, Meena Mahajan
Given a bipartite graph G = (X ˙ ∪ D, E ⊆ X × D), 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...
Dynamic Matchings in Convex Bipartite Graphs (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel
Abstract. We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V, E) under a set of update operations which includes insertions and deletions of vertices and...
Maintaining Longest Paths Incrementally (2008)
Irit Katriel, Laurent Michel, Pascal Van Hentenryck
Abstract. Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This...
Propagating Knapsack Constraints in Sublinear Time ∗ (2008)
Irit Katriel, Meinolf Sellmann, Eli Upfal, Pascal Van Hentenryck
We develop an efficient incremental version of an existing cost-based filtering algorithm for the knapsack constraint. On a universe of n elements, m invocations of the algorithm require a total of...
Multiconsistency and robustness with global constraints (2008)
Khaled Elbassioni, Irit Katriel
Abstract. We propose a natural generalization of arc-consistency, which we call multiconsistency: A value v in the domain of a variable x is kmulticonsistent with respect to a constraint C if there...
Dynamic Matchings in Convex Bipartite Graphs (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel
Abstract. We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V, E) under a set of update operations which includes insertions and deletions of vertices and...
www.cs.uu.nl Online Topological Ordering (2008)
Irit Katriel, Hans L. Bodlaender, Irit Katriel, Hans L. Bodlaender
Abstract. 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})...
An O(n log n) Version of the Averbakh-Berman Algorithm for the Robust Median of a Tree ⋆ (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Irit Katriel
Abstract. We show that the minmax regret median of a tree can be found in O(nlog n) time. This is obtained by a modification of Averbakh and Berman’s O(nlog 2 n)-time algorithm: We design a dynamic...
A Characterization of the Degree Sequences of 2-trees (2008)
It is shown that given a sequence of integers = 1 ; d 2 ; : : : ; d n >, it is possible in O(n) time to determine whether there exists a 2-tree that realizes the degree sequence , and if so, to...
Simultaneous matchings: Hardness and approximation (2008)
Kutz, Martin, Elbassioni, Khaled, Katriel, Irit, Mahajan, Meena
Irit Katriel, Irit Katriel, Peter S, Peter S, Jesper Larsson Tra
We present a simple new algorithm for computing minimum spanning trees that is more than two times faster than the best previously known algorithms (for dense, \dicult " inputs). It is of...
Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems (2007)
Irit Katriel, Claire Kenyon-mathieu, Eli Upfal
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...
Contraintes de Partitionnement par des Arbres (2006)
Beldiceanu, Nicolas, Lorca, Xavier, Katriel, Irit
Nous présentons deux contraintes qui partitionnent les sommets d'un graphe non-orienté G = (V, E), où |V| = n et |E| = m, en un ensemble d'arbres disjoints. La première contrainte,...
Contraintes de Partitionnement par des Arbres (2006)
Beldiceanu, Nicolas, Lorca, Xavier, Katriel, Irit
Nous présentons deux contraintes qui partitionnent les sommets d'un graphe non-orienté G = (V, E), où |V| = n et |E| = m, en un ensemble d'arbres disjoints. La première contrainte,...
Contraintes de Partitionnement par des Arbres (2006)
Beldiceanu, Nicolas, Lorca, Xavier, Katriel, Irit
Nous présentons deux contraintes qui partitionnent les sommets d'un graphe non-orienté G = (V, E), où |V| = n et |E| = m, en un ensemble d'arbres disjoints. La première contrainte,...
Undirected Forest Constraints (2006)
Nicolas Beldiceanu, Irit Katriel, Xavier Lorca
Abstract. We present two constraints that partition the vertices of an undirected n-vertex, m-edge graph G = (V, E) into a set of vertex-disjoint trees. The first is the resource-forest constraint,...
Faster algorithms for computing longest common increasing subsequences (2006)
Gerth Sto/lting Brodal, Kanela Kaligosi, Irit Katriel, Martin Kutz
1 Introduction Algorithms that search for the longest common subsequence (LCS) of twoinput sequences or the longest increasing subsequence (LIS) of one input sequence date back several decades.
Filtering Algorithms for the Same and UsedBy Constraints (2006)
Beldiceanu, Nicolas, Katriel, Irit, Thiel, Sven
We define the \Same\ and \UsedBy\ constraints. \UsedBy\ takes two sets of variables $X$ and $Z$ such that $|X|\ge |Z|$ and assigns values to them such that the multiset of values assigned to the...
Faster Algorithms for Computing Longest Common Increasing Subsequences (2006)
Brodal, Gerth Stølting, Kaligosi, Kanela, Katriel, Irit, Kutz, Martin, Moshe, Lewenstein, Gabriel, Valiente
We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths $m$ and $n$, where $m\ge n$, we present an algorithm with an...
Constraints and Changes (2005)
This thesis consists of four technical chapters. The first two chapters deal with filtering algorithms for global constraints. Namley, we show improved algorithms for the well known Global...
Constraints and Changes (2005)
This thesis consists of four technical chapters. The first two chapters deal with filtering algorithms for global constraints. Namley, we show improved algorithms for the well known Global...
Constraints and changes / (2005)
Saarbrücken, University, Diss., 2005 (Nicht für den Austausch).
Sub-Optimality Approximation (2005)
Russell Bent, Irit Katriel, Pascal Van Hentenryck
Abstract. The sub-optimality approximation problem considers an optimization problem O, its optimal solution σ ∗ , and a variable x with domain {d1,..., dm} and returns approximations to O[x ←...
GCC-like Restrictions on the Same Constraint (2005)
Nicolas Beldiceanu, Irit Katriel, Sven Thiel
The Same constraint takes two sets of variables X and Z such that jX j = jZj and assigns values to them such that the multiset of values assigned to the variables in X is equal to the multiset of...
Faster Algorithms for Computing Longest Common Increasing Subsequences (2005)
Gerth Søtlting Brodal, Kanela Kaligosi, Irit Katriel, Martin Kutz, Martin Kutz, Gerth Stølting, ...
We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths m and n, where m n, we present an algorithm with an...
Khaled Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan
Given a bipartite graph G = (X D, E D), an X- perfect matching is a matching in G that saturates every node in X. In this paper we study the following generalisation of the X-perfect matching...
Tree Decompositions With Small Cost (2005)
Irit Katriel Hans, Irit Katriel, Hans L. Bodlaender, Hans L. Bodlaender
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 log n}) time, an improvement over the best...
Khaled Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan
Abstract. Given a bipartite graph G = (X ˙ ∪ D, E ⊆ X × D), an Xperfect matching is a matching in G that saturates every node in X. In this paper we study the following generalisation of the...
Gerth Stølting Brodal, Kanela Kaligosi, Irit Katriel, Martin Kutz, Martin Kutz, Gerth Stølting, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Complete Bound Consistency for the Global Cardinality Constraint (2005)
We show an algorithm for bound consistency of {\em global cardinality constraints}, which runs in time $O(n+n')$ plus the time required to sort the assignment variables by range endpoints, where $n$...
Multiconsistency and Robustness with Global Constraints (2005)
Elbassioni, Khaled, Katriel, Irit, Barták, Roman, Milano, Michela
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...
GCC-like Restrictions on the Same constraint (2005)
Beldiceanu, Nicolas, Katriel, Irit, Thiel, Sven, Faltings, Boi, Petcu, Adrian, Fages, Francois, ...
The \Same\ constraint takes two sets of variables $X$ and $Z$ such that $|X|=|Z|$ and assigns values to them such that the multiset of values assigned to the variables in $X$ is equal to the multiset...
Online Topological Ordering (2005)
Katriel, Irit, Bodlaender, Hans L.
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\})$...
Filtering algorithms for the Same constraint (2004)
Beldiceanu,Nicolas, Katriel,Irit, Thiel,Sven
We define the \Same\ and \UsedBy\ constraints. \UsedBy\ takes two sets of variables $X$ and $Z$ such that $|X|\ge |Z|$ and assigns values to them such that the multiset of values assigned to the...
On the Algebraic Complexity of Set Equality and Inclusion (2004)
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...
Dynamic Heaviest Paths in DAGs with Arbitrary Edge Weights (2004)
Katriel, Irit, Régin, Jean-Charles, Rueher, Michel
We deal with the problem of maintaining the heaviest paths in a DAG under edge insertion and deletion. Michel and Van Hentenryck~\cite{Michel} designed algorithms for this problem which work on DAGs...
Filtering algorithms for the Same constraint (2004)
Beldiceanu, Nicolas, Katriel, Irit, Thiel, Sven, Régin, Jean-Charles, Rueher, Michel
We define the \Same\ and \UsedBy\ constraints. \UsedBy\ takes two sets of variables $X$ and $Z$ such that $|X|\ge |Z|$ and assigns values to them such that the multiset of values assigned to the...
Filtering Algorithms for the Same and UsedBy Constraints (2004)
Nicolas Beldiceanu, Irit Katriel, Sven Thiel
We define the Same and UsedBy constraints. UsedBy takes two sets of variables X and Z such that jX j jZj and assigns values to them such that the multiset of values assigned to the variables in Z is...
Filtering algorithms for the Same constraint (2004)
Beldiceanu, Nicolas, Katriel, Irit, Thiel, Sven, Régin, Jean-Charles, Rueher, Michel
We define the \Same\ and \UsedBy\ constraints. \UsedBy\ takes two sets of variables $X$ and $Z$ such that $|X|\ge |Z|$ and assigns values to them such that the multiset of values assigned to the...
On the Algebraic Complexity of Set Equality and Inclusion (2004)
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...
Dynamic Heaviest Paths in DAGs with Arbitrary Edge Weights (2004)
Katriel, Irit, Régin, Jean-Charles, Rueher, Michel
We deal with the problem of maintaining the heaviest paths in a DAG under edge insertion and deletion. Michel and Van Hentenryck~\cite{Michel} designed algorithms for this problem which work on DAGs...
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property (2003)
Katriel, Irit, Sanders, Peter, Träff, Jesper Larsson, Di Battista, Giuseppe, Zwick, Uri
Elementary Graph Algorithms in External Memory (2003)
Katriel, Irit, Meyer, Ulrich, Meyer, Ulrich, Sanders, Peter, Sibeyn, Jop
A practical minimum spanning tree algorithm using the cycle property (2003)
Irit Katriel, Peter Sanders, Jesper Larsson Tra
Abstract. We present a simple new (randomized) algorithm for computing minimum spanning trees that is more than two times faster than the best previously known algorithms (for dense, \dicult...
Fast Bound Consistency for the Global Cardinality Constraint (2003)
We show an algorithm for bound consistency of global cardi- nality constraints, which runs in time O(n+n ) plus the time required to sort the assignment variables by range endpoints, where n is the...