Scalar Aggregation in Inconsistent Databases \Lambda (2009)
Vijay Raghavan, Jeremy Spinrad
Abstract We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest lowest/least...
Marcelo Arenas, Vijay Raghavan, Leopoldo Bertossi, Xin He, Jeremy Spinrad
We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest lowest/least upper bounds...
Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny (2008)
Anne Berry, Alain Sigayret, Jeremy Spinrad
Abstract. We improve the current complexities for maintaining a chordal graph by starting with an empty graph and repeatedly adding or deleting edges. 1
Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny (2008)
Anne Berry, Alain Sigayret, Jeremy Spinrad
Abstract. We improve the current complexities for maintaining a chordal graph by starting with an empty graph and repeatedly adding or deleting edges. 1
www.cs.uu.nl On Algorithms for (P5,Gem)-Free Graphs (2008)
Hans L. Bodlaender, Andreas Brandstädt, Dieter Kratsch, Michaël Rao, Jeremy Spinrad, Städt Dieter Kratsch, ...
A graph is (P5,gem)-free, when it does not contain P5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced...
Faster deterministic and randomized algorithms on the Homogeneous Set Sandwich Problem (2008)
Abstract. A homogeneous set is a non-trivial, proper subset of a graph’s vertices such that all its elements present exactly the same outer neighborhood. Given two graphs, G1(V, E1), G2(V, E2), we...
Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number (2007)
Stefan Felsner, Vijay Raghavan, Jeremy Spinrad
. Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be...
Forbidden subgraph decomposition (2007)
I. Rusu, J. Spinrad, Irena Rusu, Jeremy Spinrad
We dene a new form of graph decomposition, based on forbidding a xed bipartite graph from occurring as an induced subgraph of edges which cross a partition of the vertices. We show that some natural...
Abstract. A homogeneous set is a non-trivial, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs, G1(V, E1), G2 (V, E2),...
Polynomial time recognition of unit circular-arc graphs (2006)
Durán, Guillermo, Gravano, Agustín, McConnell, Ross M., Spinrad, Jeremy, Tucker, Alan
We present an efficient algorithm for recognizing unit circular-arc (UCA) graphs, based on a characterization theorem for UCA graphs proved by Tucker in the seventies. Given a proper circular-arc...
On Algorithms for (P_5,Gem)-Free Graphs (2003)
Hans L. Bodlaender, Andreas Brandstädt, Andreas Brandst Adt, Dieter Kratsch, Micha El Rao, ...
A graph is (P 5 ,gem)-free, when it does not contain P 5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the...