Search

Your search keyword '"Crescenzi, Pierluigi"' showing total 328 results
Start Over Author "Crescenzi, Pierluigi"
328 results on '"Crescenzi, Pierluigi"'

151. High Spies (or How to Win a Programming Contest).

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, Deutz, André, and Vliet, Rudy

Abstract

We analyse transports between leaves in an edge-weighted tree. We prove under which conditions there exists a transport matching the weights of a given tree. We use this to compute minimum and maximum values for the transport between a given pair of leaves. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

152. Efficient Algorithms for the Spoonerism Problem.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, Böckenhauer, Hans-Joachim, and Hromkovič, Juraj

Abstract

A spoonerism is a sentence in some natural language where the swapping of two letters results in a new sentence with a different meaning. In this paper, we give some efficient algorithms for deciding whether a given sentence, made up from words of a given dictionary, is a spoonerism or not. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

153. Pictures from Mongolia - Partial Sorting in a Partial World.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, Boldi, Paolo, and Chierichetti, Flavio

Abstract

You are back from that very long, marvelous journey. You have a thousand pictures, but your friends and relatives will stand just a few dozens. Choosing is a painful process, in particular when you cannot decide between the silent vastity of that desert and the idyllic picture of that tranquil, majestic lake. We are going to help. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

154. Knitting for Fun: A Recursive Sweater.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, Bernasconi, Anna, and Bodei, Chiara

Abstract

In this paper we investigate the relations between knitting and computer science. We show that the two disciplines share many concepts. Computer science, in particular algorithm theory, can suggest a lot of powerful tools that can be used both in descriptive and prescriptive ways and that apparently have not yet been used for creative knitting. The obtained results are short (optimal size) recursive descriptions for complex patterns; creation of new complex recursive patterns; and the application of three-valued algebra operations to combine and create a wide variety of new patterns. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

155. Tablatures for Stringed Instruments and Generating Functions.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, Baccherini, Davide, and Merlini, Donatella

Abstract

We study some combinatorial properties related to the problem of tablature for stringed instruments. First, we describe the problem in a formal way and prove that it is equivalent to a finite state automaton. We define the concepts of distance between two chords and tablature complexity in order to study the problem of tablature in terms of music performance. By using the Schützenberger methodology we are then able to find the generating function counting the number of tablatures having a certain complexity and we can study the average complexity for the tablatures of a music score. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

156. HIROIMONO Is NP-Complete.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, and Andersson, Daniel

Abstract

In a Hiroimono puzzle, one must collect a set of stones from a square grid, moving along grid lines, picking up stones as one encounters them, and changing direction only when one picks up a stone. We show that deciding the solvability of such puzzles is NP-complete. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

157. Wooden Geometric Puzzles: Design and Hardness Proofs.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, Alt, Helmut, and Bodlaender, Hans

Abstract

We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the solution of puzzles leads to interesting questions, but also puzzle design gives rise to interesting theoretical questions. This leads to the search for instances of partition that use only integers and are uniquely solvable. We show that instances of polynomial size exist with this property. This result also holds for partition into k subsets with the same sum: We construct instances of n integers with subset sum O(nk + 1), for fixed k. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

158. On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, Battista, Giuseppe, and Frati, Fabrizio

Abstract

Graph Drawing is (usually) concerned with the production of readable representations of graphs. In this paper, instead of investigating how to produce "good" drawings, we tackle the opposite problem of producing "bad" drawings. In particular, we study how to construct orthogonal drawings with many bends along the edges and with large area. Our results show surprising contact points, in Graph Drawing, between the computational cost of niceness and the one of ugliness. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

175. Fun with Sub-linear Time Algorithms.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, and Trevisan, Luca

Abstract

Provided that one is willing to use randomness and to tolerate an approximate answer, many computational problems admit ultra-fast algorithms that run in less than linear time in the length of the input. In many interesting cases, even algorithms that run in constant time are known, whose efficiency depends only on the accuracy of the approximation and not on the length of the inputs. Algorithms for graph problems on dense graphs are especially efficient and simple. I will describe an algorithm that estimates the size of the maximum cut in a dense graph, and its specialization to the task of distinguishing bipartite dense graphs from dense graphs that are "far from bipartite." Results "explaining" the simplicity of such algorithms will also be discussed. Some sublinear-time algorithms are also known for graph problems in sparse graphs, but they are typically more elaborate. I will describe a simple but very clever algorithm that approximates the number of connected components of a given graph, and its generalization to the problem of approximating the weight of the minimum spanning tree of a given weighted graph. The algorithm runs in time dependent only on the maximum degree, the required quality of approximation, and the range of weights, but the running time is independent of the number of vertices. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

176. Close Encounters with a Black Hole or Explorations and Gatherings in Dangerous Graphs.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Crescenzi, Pierluigi, Prencipe, Giuseppe, Pucci, Geppino, and Santoro, Nicola

Abstract

Consider a netscape inhabited by mobile computational entities (e.g., robots, agents, sensors). In the algorithmic literature, these environments are usually assumed to be safe for the entities. Outside of the literature, this is hardly the case: highly harmful objects can operate in the netscape rendering the environment dangerous for the entities. A particular example is the presence of a black hole: a network site (node, host) that disposes of any incoming robot/agent, leaving no observable trace of such a destruction. The reasons why a node becomes a black hole are varied; for example, the presence at a node of a harmful static process (e.g., a virus) that destroys incoming code and messages transforms that node into a black hole; the undetectable crash failure of a host renders that host a black hole; "receive-omission" failures in the communication software of a site makes that site act as a black hole. Indeed, this type of danger is not rare. Clearly the presence of a black hole renders computations in the net dangerous to be performed, and some tasks become impossible to be carried out. We will examine two classic problems for mobile entities, Exploration and Gathering (or Rendezvous), and discuss how they are affected by the presence of a black hole. In particular, we will view them with respect to a new task that, in this context, is even more basic and essential: Black Hole Search, the problem of a team of mobile entities locating the black hole. Obviously, any entity entering the black hole is destroyed; the black hole location problem is solved if at least one agent survives, and all surviving agents know the location of the black hole. Not satisfied with correctness, our focus is on efficiency. The basic cost measures are the number of entities (and of casualties), and the number of moves. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

177. Web Marshals Fighting Curly Link Farms

Author

Luccio, Fabrizio, Pagli, Linda, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

178. Pictures from Mongolia – Partial Sorting in a Partial World

Author

Boldi, Paolo, Chierichetti, Flavio, Vigna, Sebastiano, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

179. Efficient Algorithms for the Spoonerism Problem

Author

Böckenhauer, Hans-Joachim, Hromkovič, Juraj, Královič, Richard, Mömke, Tobias, Steinhöfel, Kathleen, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

180. Drawing Borders Efficiently

Author

Iwama, Kazuo, Miyano, Eiji, Ono, Hirotaka, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

181. Tablatures for Stringed Instruments and Generating Functions

Author

Baccherini, Davide, Merlini, Donatella, Sprugnoli, Renzo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

182. Knitting for Fun: A Recursive Sweater

Author

Bernasconi, Anna, Bodei, Chiara, Pagli, Linda, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

183. Wooden Geometric Puzzles: Design and Hardness Proofs

Author

Alt, Helmut, Bodlaender, Hans, van Kreveld, Marc, Rote, Günter, Tel, Gerard, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

184. On the Complexity of the Traffic Grooming Problem in Optical Networks : (Extended Abstract)

Author

Shalom, Mordechai, Unger, Walter, Zaks, Shmuel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

185. HIROIMONO Is NP-Complete

Author

Andersson, Daniel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

186. The Ferry Cover Problem

Author

Lampis, Michael, Mitsou, Valia, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

187. Intruder Capture in Sierpiński Graphs

Author

Luccio, Flaminia L., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

188. On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features

Author

Di Battista, Giuseppe, Frati, Fabrizio, Patrignani, Maurizio, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

189. Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles

Author

Gradwohl, Ronen, Naor, Moni, Pinkas, Benny, Rothblum, Guy N., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

190. The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake

Author

Holzer, Markus, Ruepp, Oliver, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

191. Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms

Author

Gruber, Hermann, Holzer, Markus, Ruepp, Oliver, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

192. Approximating Rational Numbers by Fractions

Author

Forišek, Michal, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

193. The Worst Page-Replacement Policy

Author

Agrawal, Kunal, Bender, Michael A., Fineman, Jeremy T., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

194. Die Another Day

Author

Fleischer, Rudolf, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

195. The Traveling Beams Optical Solutions for Bounded NP-Complete Problems : (Extended Abstract)

Author

Dolev, Shlomi, Fitoussi, Hen, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

196. Robots and Demons (The Code of the Origins)

Author

Dieudonné, Yoann, Petit, Franck, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

197. High Spies (or How to Win a Programming Contest)

Author

Deutz, André, van Vliet, Rudy, Hoogeboom, Hendrik Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

198. Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

Author

Acuña, Vicente, Birmelé, Etienne, Cottret, Ludovic, Crescenzi, Pierluigi, Jourdan, Fabien, Lacroix, Vincent, Marchetti-Spaccamela, Alberto, Marino, Andrea, Milreu, Paulo Vieira, Sagot, Marie-France, and Stougie, Leen

Subjects
*SET theory, *DIRECTED acyclic graphs, *CONSTRAINT satisfaction, *POLYNOMIALS, *ALGORITHMS, *MATHEMATICAL analysis
Abstract

Abstract: We present a constrained version of the problem of enumerating all maximal directed acyclic subgraphs (DAG) of a graph . In this version, we enumerate maximal DAGs whose sources and targets belong to a predefined subset of the nodes. We call such DAGs stories. We first show how to compute one story in polynomial-time, and then describe two different algorithms to “tell” all possible stories. [Copyright &y& Elsevier]

Published
2012
Full Text
View/download PDF

199. Close Encounters with a Black Hole or Explorations and Gatherings in Dangerous Graphs

Author

Santoro, Nicola, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

200. Fun with Sub-linear Time Algorithms

Author

Trevisan, Luca, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Crescenzi, Pierluigi, editor, Prencipe, Giuseppe, editor, and Pucci, Geppino, editor

Published
2007
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results