Author name cluster

Jeremy Spinrad

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2005 Journal Article

On algorithms for ( P 5,gem)-free graphs

Hans L. Bodlaender
Andreas Brandstädt
Dieter Kratsch
Michaël Rao
Jeremy Spinrad

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 induced path P 4 ) as an induced subgraph. We present O ( n 2 ) time recognition algorithms for chordal gem-free graphs and for ( P 5, gem)-free graphs. Using a characterization of ( P 5, gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [A. Brandstädt, D. Kratsch, On the structure of ( P 5, gem)-free graphs, Discrete Appl. Math. 145 (2005), 155–166], we give linear time algorithms for the following NP-complete problems on ( P 5, gem)-free graphs: Minimum Coloring; Maximum Weight Stable Set; Maximum Weight Clique; and Minimum Clique Cover.

Details DOI

TCS Journal 2003 Journal Article

Scalar aggregation in inconsistent databases

Marcelo Arenas
Leopoldo Bertossi
Jan Chomicki
Xin He
Vijay Raghavan
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 on the value of the scalar function across all (minimal) repairs of the database. We show how to compute such answers. We provide a complete characterization of the computational complexity of this problem. We also show how tractability can be improved in several special cases (one involves a novel application of Boyce–Codd Normal Form) and present a practical hybrid query evaluation method.

Details DOI

TCS Journal 1997 Journal Article

On treewidth and minimum fill-in of asteroidal triple-free graphs

Ton Kloks
Dieter Kratsch
Jeremy Spinrad

We present O(n 5 R + n 3 R 3) time algorithms to compute the treewidth, pathwidth, minimum fill-in and minimum interval graph completion of asteroidal triple-free graphs, where n is the number of vertices and R is the number of minimal separators of the input graph. This yields polynomial time algorithms for the four NP-complete graph problems on any subclass of the asteroidal triple-free graphs that has a polynomially bounded number of minimal separators, as e. g. cocomparability graphs of bounded dimension and d-trapezoid graphs for any fixed d ⩾ 1.

Details DOI