Experimental Validation in Large-Scale Systems: a Survey of Methodologies (2009)
Gustedt, Jens, Jeannot, Emmanuel, Quinson, Martin
The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes...
Experimental Validation in Large-Scale Systems: a Survey of Methodologies (2009)
Gustedt, Jens, Jeannot, Emmanuel, Quinson, Martin
The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes...
Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient (2009)
Commonly used techniques for the random generation of graphs such as those of Erdős & Rényi and Barabási & Albert have two disadvantages, namely their lack of bias with respect to history of the...
Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient (2009)
Commonly used techniques for the random generation of graphs such as those of Erdős & Rényi and Barabási & Albert have two disadvantages, namely their lack of bias with respect to history of the...
Experimental Validation in Large-Scale Systems: a Survey of Methodologies (2009)
Gustedt, Jens, Jeannot, Emmanuel, Quinson, Martin
The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes...
Experimental Validation in Large-Scale Systems: a Survey of Methodologies (2009)
Gustedt, Jens, Jeannot, Emmanuel, Quinson, Martin
The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes...
Experimenting Iterative Computations with Ordered Read-Write Locks (2009)
Clauss, Pierre-Nicolas, Gustedt, Jens
This paper presents the first experimental results of the use of our new adaptive tool for synchronization, based on ordered read-write locks, ORWL. They provide a new synchronizing method for...
Experimenting Iterative Computations with Ordered Read-Write Locks (2009)
Clauss, Pierre-Nicolas, Gustedt, Jens
This paper presents the first experimental results of the use of our new adaptive tool for synchronization, based on ordered read-write locks, ORWL. They provide a new synchronizing method for...
parXXL: A Fine Grained Development Environment on Coarse Grained Architectures (2008)
Jens Gustedt, Stéphane Vialle, Amelia De Vivo, Inria Lorraine
Abstract. We present a new integrated environment for cellular computing and other fine grained applications. It is based upon previous developments concerning cellular computing environments (the...
The parXXL Environment: Scalable Fine Grained Development for Large Coarse Grained Platforms (2008)
Jens Gustedt, Stéphane Vialle, Amelia De Vivo
Abstract. We present a new integrated environment for cellular computing and other fine grained applications. It is based upon previous developments concerning cellular computing environments (the...
Isabelle Guérin Lassous, Jens Gustedt, Inria Lorraine
We present and analyze two portable algorithms for the List Ranking Problem in the Coarse Grained Multicomputer model (CGM). We report on implementations of these algorithms and experiments that were...
Assefaw Hadish Gebremedhin, Jens Gustedt, Inria Lorraine, Isabelle Guérin Lassous, Jan Arne Telle
We present a new parallel computation model that enables the design of resource-optimal and scalable parallel algorithms and simplifies their analysis. The model rests on the following novel ideas:...
Assefaw Hadish Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle
Abstract. We present a new parallel computation model called the Parallel Resource-Optimal computation model. PRO is a framework being proposed to enable the design of efficient and scalable parallel...
PRO: a Model for Parallel Resource-Optimal (2008)
Assefaw Hadish, Gebremedhin Isabelle, Jens Gustedt, Jan Arne Telle
Computation *
Graph Coloring on Coarse Grained Multicomputers* (2008)
Assefaw Hadish, Gebremedhin Isabelle, Jens Gustedt, Jan Arne Telle
Abstract We present an efficient and scalable Coarse Grained Multicomputer(CGM) coloring algorithm that colors a graph G with at most \Delta + 1colors where \Delta is the maximum degree in G. This...
Graph Coloring on Coarse Grained Multicomputers ∗ (2008)
Assefaw Hadish, Gebremedhin Isabelle, Guérin Lassous, Jens Gustedt, Jan Arne Telle
We present an efficient and scalable Coarse Grained Multicomputer (CGM) coloring algorithm that colors a graph G with at most ∆ + 1 colors where ∆ is the maximum degree in G. This algorithm is...
PRO: a Model for Parallel Resource-Optimal Computation ∗ (2008)
Assefaw Hadish, Gebremedhin Isabelle, Guérin Lassous, Jens Gustedt, Jan Arne Telle
We present a new parallel computation model that enables the design of resource-optimal scalable parallel algorithms and simplifies their analysis. The model rests on the novel idea of incorporating...
Efficient Sampling of Random Permutations (2008)
We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external...
Efficient Sampling of Random Permutations (2008)
We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external...
Out-of-Core Wavefront Computations with Reduced Synchronization (2008)
Clauss, Pierre-Nicolas, Gustedt, Jens, Suter, Frédéric
Matrix computation algorithms often exhibit dependencies between neighboring elements inside loop nests such that the frontier between computed elements and those to be computed wanders in form of a...
Out-of-Core Wavefront Computations with Reduced Synchronization (2008)
Clauss, Pierre-Nicolas, Gustedt, Jens, Suter, Frédéric
Matrix computation algorithms often exhibit dependencies between neighboring elements inside loop nests such that the frontier between computed elements and those to be computed wanders in form of a...
Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient (2008)
Commonly used techniques for the random generation of graphs have two disadvantages, namely their lack of bias with respect to history of the evolution of the graph, and their incapability to produce...
Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient (2008)
Commonly used techniques for the random generation of graphs have two disadvantages, namely their lack of bias with respect to history of the evolution of the graph, and their incapability to produce...
Iterative Computations with Ordered Read-Write Locks (2008)
Clauss, Pierre-Nicolas, Gustedt, Jens
We introduce the framework of ordered read-write locks, ORWL, that are characterized by two main features: a strict FIFO policy for access and the attribution of access to lock-handles instead of...
Iterative Computations with Ordered Read-Write Locks (2008)
Clauss, Pierre-Nicolas, Gustedt, Jens
We introduce the framework of ordered read-write locks, ORWL, that are characterized by two main features: a strict FIFO policy for access and the attribution of access to lock-handles instead of...
Multi-Site Emulation using Wrekavoc: Validating Distributed Algorithms and Applications (2008)
Dubuisson, Olivier, Gustedt, Jens, Jeannot, Emmanuel
Experimental validation and testing of solutions designed for heterogeneous environment is a challenging issue. Wrekavoc is a tool for performing such validation. It runs an unmodified applications...
Multi-Site Emulation using Wrekavoc: Validating Distributed Algorithms and Applications (2008)
Dubuisson, Olivier, Gustedt, Jens, Jeannot, Emmanuel
Experimental validation and testing of solutions designed for heterogeneous environment is a challenging issue. Wrekavoc is a tool for performing such validation. It runs an unmodified applications...
Numerical results for generalized attachment models for the genesis of graphs (2008)
Using the network generation model from Gustedt 2008, we simulate and analyze the clustering coefficient of the networks as some parameters changes
Numerical results for generalized attachment models for the genesis of graphs (2008)
Using the network generation model from Gustedt 2008, we simulate and analyze the clustering coefficient of the networks as some parameters changes
Stefan Felsner, Jens Gustedt, Michel Morvan
Abstract. We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have...
J. A. Telle, Assefaw Hadish, Gebremedhin Isabelle, Gurin Lassous, Jens Gustedt, Jan Arne Telle
PRO: a model for Parallel Resource-Optimal computation
Assefaw Hadish Gebremedhin, Isabelle Guerin Lassous, Jens Gustedt, Jan Arne Telle
Abstract. We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph G with a guarantee of at most D G +1 colors. 1 Introduction and Overview The problem of...
Assefaw Hadish Gebremedhin, Jens Gustedt, Jan Arne Telle
We present an efficient and scalable Coarse Grained Multicomputer (CGM) coloring algorithm that colors a graph G with at most D+ 1 colors where D is the maximum degree in G. This algorithm is given...
Abstract. The Lexicographically First Maximal Independent Set Problem on graphs with bounded degree 3 is P-complete, and thus not parallelizable in a fine-grained setting unless P=NC. On the other...
Specifying Filter Characteristics with FilterPro (2007)
Jens Gustedt, Jens Gustedt, Tu Berlin, Tu Berlin
FilterPro is a formal language that was created to facilitate the consistent formulation of design problems for digital filters. It was developed in the project IFP Digitale Filter
ALGORITHMIC ASPECTS OF ORDERED STRUCTURES vorgelegt von Diplom-Mathematiker (2007)
Jens Gustedt, Vom Fachbereich Mathematik, Vorsitzender Prof, Dr. G Frank
Dann geben wir ein allgemeines 0-1-Gesetz f ur erbliche Eigenschaften, das Auswirkungen f ur die mittlere Komplexit at hat. Dieses Ergebnis f ur mittlere Komplexit at wird auf die Klasse der...
PRO: a Model for Parallel Resource-Optimal Computation (2007)
Assefaw Hadish Gebremedhin, Gebremedhin Isabelle, Isabelle Guerin Lassous, Jens Gustedt, Jan Arne Telle
We present a new parallel computation model that enables the design of resource-optimal scalable parallel algorithms and simplifies their analysis. The model rests on the novel idea of incorporating...
Constructing Colorings for Diagrams (2007)
Stefan Felsner, Jens Gustedt, Michel Morvan, Jean-xavier Rampon
Introduction and Overview An undirected graph G = (V; E) is a (Hasse--) diagram if there is a poset P = (V; !) and an orientation ~ E of E such that (x; y) 2 ~ E iff x ! y in P and there is no z with...
An Interactive Problem Modeller and PDE Solver, Distributed on Large Scale Architectures (2007)
Fressengeas, Nicolas, Frezza-Buet, Hervé, Gustedt, Jens, Vialle, Stéphane
This paper introduces a research project and a software environment to speed up and size up problem modeling with Partial Differential Equations (PDE). These PDE are defined from a \Mathematica...
An Interactive Problem Modeller and PDE Solver, Distributed on Large Scale Architectures (2007)
Fressengeas, Nicolas, Frezza-Buet, Hervé, Gustedt, Jens, Vialle, Stéphane
This paper introduces a research project and a software environment to speed up and size up problem modeling with Partial Differential Equations (PDE). These PDE are defined from a \Mathematica...
Sublinear Communication for Integer Permutations (2007)
In [\cite{GUSTEDT:2006:INRIA-00000900:2}] we have shown that random shuffling of data can be realised with linear resource usage, CPU time as well as communication, and this for a large variaty of...
Sublinear Communication for Integer Permutations (2007)
In [\cite{GUSTEDT:2006:INRIA-00000900:2}] we have shown that random shuffling of data can be realised with linear resource usage, CPU time as well as communication, and this for a large variaty of...
The parXXL Environment: Scalable Fine Grained Development for Large Coarse Grained Platforms (2007)
Gustedt, Jens, Vialle, Stéphane, De Vivo, Amelia
We present a new integrated environment for cellular computing and other fine grained applications. It is based upon previous developments concerning cellular computing environments (the ParCeL...
The parXXL Environment: Scalable Fine Grained Development for Large Coarse Grained Platforms (2007)
Gustedt, Jens, Vialle, Stéphane, De Vivo, Amelia
We present a new integrated environment for cellular computing and other fine grained applications. It is based upon previous developments concerning cellular computing environments (the ParCeL...
An experimental validation of the PRO model for parallel and distributed computation (2006)
Essaïdi, Mohamed, Gustedt, Jens
The Parallel Resource-Optimal (PRO) computation model was introduced by Gebremedhin et al. [2002] as a framework for the design and analysis of efficient parallel algorithms. The key features of the...
Bounded Arboricity to Determine the Local Structure of Sparse Graphs (2006)
A known approach of detecting dense subgraphs communities in large sparse graphs involves first computing the probability~vectors for short random~walks on the graph, and then using these probability...
Bounded Arboricity to Determine the Local Structure of Sparse Graphs (2006)
A known approach of detecting dense subgraphs communities in large sparse graphs involves first computing the probability~vectors for short random~walks on the graph, and then using these probability...
parXXL: A Fine Grained Development Environment on Coarse Grained Architectures (2006)
Gustedt, Jens, Vialle, Stéphane, De Vivo, Amelia
We present a new integrated environment for cellular computing and other fine grained applications. It is based upon previous developments concerning cellular computing environments (the ParCeL...
parXXL: A Fine Grained Development Environment on Coarse Grained Architectures (2006)
Gustedt, Jens, Vialle, Stéphane, De Vivo, Amelia
We present a new integrated environment for cellular computing and other fine grained applications. It is based upon previous developments concerning cellular computing environments (the ParCeL...
PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms (2006)
Gebremedhin, Assefaw Hadish, Gustedt, Jens, Essaïdi, Mohamed, Guérin Lassous, Isabelle, Telle, Jan Arne
We present a new parallel computation model called the Parallel Resource-Optimal computation model. PRO is a framework being proposed to enable the design of efficient and scalable parallel...
parXXL: A Fine Grained Development Environment on Coarse Grained Architectures (2006)
Gustedt, Jens, Vialle, Stéphane, De Vivo, Amelia
We present a new integrated environment for cellular computing and other fine grained applications. It is based upon previous developments concerning cellular computing environments (the ParCeL...
Bounded Arboricity to Determine the Local Structure of Sparse Graphs (2006)
A known approach of detecting dense subgraphs communities in large sparse graphs involves first computing the probability~vectors for short random~walks on the graph, and then using these probability...
An experimental validation of the PRO model for parallel and distributed computation (2006)
Essaïdi, Mohamed, Gustedt, Jens
The Parallel Resource-Optimal (PRO) computation model was introduced by Gebremedhin et al. [2002] as a framework for the design and analysis of efficient parallel algorithms. The key features of the...
PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms (2006)
Gebremedhin, Assefaw Hadish, Gustedt, Jens, Essaïdi, Mohamed, Guérin Lassous, Isabelle, Telle, Jan Arne
We present a new parallel computation model called the Parallel Resource-Optimal computation model. PRO is a framework being proposed to enable the design of efficient and scalable parallel...
Data Handover: Reconciling Message Passing and Shared Memory (2006)
Data Handover (DHO) is a programming paradigm and interface that aims to handle data between parallel or distributed processes that mixes aspects of message passing and shared memory. It is designed...
PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms (2005)
Gebremedhin, Assefaw, Guérin Lassous, Isabelle, Gustedt, Jens, Telle, Jan Arne
We present a new parallel computation model that enables the design of resource-optimal and scalable parallel algorithms and simplifies their analysis. The model rests on the following novel ideas:...
PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms (2005)
Gebremedhin, Assefaw, Guérin Lassous, Isabelle, Gustedt, Jens, Telle, Jan Arne
We present a new parallel computation model that enables the design of resource-optimal and scalable parallel algorithms and simplifies their analysis. The model rests on the following novel ideas:...
Efficient Sampling of Random Permutations (2005)
We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external...
Efficient Sampling of Random Permutations (2005)
We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external...
An experimental validation of the PRO model for parallel and distributed computation (2005)
Essaïdi, Mohamed, Gustedt, Jens
The Parallel Resource-Optimal (PRO) computation model was introduced by Gebremedhin et al. [2002] as a framework for the design and analysis of efficient parallel algorithms. The key features of the...
PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms (2005)
Gebremedhin, Assefaw, Gustedt, Jens, Essaïdi, Mohamed, Guérin Lassous, Isabelle, Telle, Jan Arne
We present a new parallel computation model called the Parallel Resource-Optimal computation model. PRO is a framework being proposed to enable the design of efficient and scalable parallel...
Efficient Sampling of Random Permutations (2005)
We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external...
PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms (2005)
Mohamed Essaïdi, Isabelle Guérin Lassous, Jan Arne Telle, Assefaw Hadish Gebremedhin, Jens Gustedt, Inria Lorraine
We present a new parallel computation model called the Parallel Resource-Optimal computation model. PRO is a framework being proposed to enable the design of efficient and scalable parallel...
Data Handover: Reconciling Message Passing and Shared Memory (2004)
We present a programming paradigm and interface that aims to handle data between parallel or distributed processes that mixes aspects of message passing and shared memory. It is designed to overcome...
SSCRAP : Soft Synchronized Computing in Rounds for Adequate Parallelization (2004)
Essaïdi, Mohamed, Guérin Lassous, Isabelle, Gustedt, Jens
The Soft Synchronized Computing in Round for Adequate Parallelization () library is a C++ communication and synchronization library for coarse grained algorithms. SSCRAP is the first library...
External Memory Algorithms using a Coarse Grained Paradigm (2004)
We present a simple framework that allows for the use of algorithms in external memory settings that originally were designed for coarse grained parallel architectures. This framework is an extension...
Data Handover: Reconciling Message Passing and Shared Memory (2004)
We present a programming paradigm and interface that aims to handle data between parallel or distributed processes that mixes aspects of message passing and shared memory. It is designed to overcome...
SSCRAP : Soft Synchronized Computing in Rounds for Adequate Parallelization (2004)
Essaïdi, Mohamed, Guérin Lassous, Isabelle, Gustedt, Jens
The Soft Synchronized Computing in Round for Adequate Parallelization () library is a C++ communication and synchronization library for coarse grained algorithms. SSCRAP is the first library...
External Memory Algorithms using a Coarse Grained Paradigm (2004)
We present a simple framework that allows for the use of algorithms in external memory settings that originally were designed for coarse grained parallel architectures. This framework is an extension...
External Memory Algorithms using a Coarse Grained Paradigm (2004)
We present a simple framework that allows for the use of algorithms in external memory settings that originally were designed for coarse grained parallel architectures. This framework is an extension...
SSCRAP : Soft Synchronized Computing in Rounds for Adequate Parallelization (2004)
Essaïdi, Mohamed, Guérin Lassous, Isabelle, Gustedt, Jens
The Soft Synchronized Computing in Round for Adequate Parallelization () library is a C++ communication and synchronization library for coarse grained algorithms. SSCRAP is the first library...
Data Handover: Reconciling Message Passing and Shared Memory (2004)
We present a programming paradigm and interface that aims to handle data between parallel or distributed processes that mixes aspects of message passing and shared memory. It is designed to overcome...
We present an extension to SSCRAP, our C++ environment for the development of coarse grained algorithms, that allows for easy execution of programs in an external memory setting. Our environment is...
We present an extension to SSCRAP, our C++ environment for the development of coarse grained algorithms, that allows for easy execution of programs in an external memory setting. Our environment is...
We present an extension to SSCRAP, our C++ environment for the development of coarse grained algorithms, that allows for easy execution of programs in an external memory setting. Our environment is...
Performance Implications by the Hierarchical Design of Clusters (2003)
Ben Fraj, Wissem, Essaïdi, Mohamed, Gustedt, Jens
We present experimental results for the evaluation of PC clusters that differ on several aspect of their architecture, such as being mono or biprocessors and having a high bandwidth interconnection...
Performance Implications by the Hierarchical Design of Clusters (2003)
Ben Fraj, Wissem, Essaïdi, Mohamed, Gustedt, Jens
We present experimental results for the evaluation of PC clusters that differ on several aspect of their architecture, such as being mono or biprocessors and having a high bandwidth interconnection...
Graph Coloring on Coarse Grained Multicomputers (2003)
Assefaw Hadish Gebremedhin, Gebremedhin Isabelle, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle
We present an e#cient and scalable Coarse Grained Multicomputer (CGM) coloring algorithm that colors a graph G with at most # + 1 colors where # is the maximum degree in G. This algorithm is given in...
Randomized Permutations in a Coarse Grained Parallel Environment (2002)
We show how to distribute data at random (not to be confounded with permutation routing) in a coarse grained parallel environment with $p$ processors. Previously known methods were not able to...
Randomized Permutations in a Coarse Grained Parallel Environment (2002)
We show how to distribute data at random (not to be confounded with permutation routing) in a coarse grained parallel environment with $p$ processors. Previously known methods were not able to...
Randomized Permutations in a Coarse Grained Parallel Environment (2002)
We show how to distribute data at random (not to be confounded with permutation routing) in a coarse grained parallel environment with $p$ processors. Previously known methods were not able to...
PRO: a model for Parallel Resource-Optimal computation (2002)
Assefaw Hadish Gebremedhin, Jens Gustedt
We present a new parallel computation model that enables the design of resource-optimal scalable parallel algorithms and simplifies their analysis. The model rests on the novel idea of incorporating...
PRO: a model for Parallel Resource-Optimal computation (2002)
Assefaw Hadish Gebremedhin, Isabelle Guerin Lassous, Jens Gustedt, Jan Arne Telle
We present a new parallel computation model that enables the design of resource-optimal scalable parallel algorithms and simplifies their analysis. The model rests on the novel idea of incorporating...
The treewidth of Java programs (2002)
Jens Gustedt, Ole A. Mhle, Jan Arne Telle
Intuitively, the treewidth of a graph G measures how close G is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on G, by dynamic programming along the...
Partially Complemented Representations of Digraphs (2002)
Elias Dahlhaus, Jens Gustedt, Ross M. McConnell
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent...
Partially complemented representations of digraphs (2002)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent...
Partially complemented representations of digraphs (2002)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent...
The Treewidth of Java Programs (2001)
Gustedt, Jens, Maehle, Ole A., Telle, Jan Arne
Intuitively, the treewidth of a graph $G$ measures how close $G$ is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on $G$, by dynamic programming...
PRO: a model for Parallel Resource-Optimal Computation (2001)
Gustedt, Jens, Telle, Jan Arne, Gebremedhin, Assefaw Hadish, Guérin Lassous, Isabelle
We present a new parallel computational model that enables the design of resource-optimal scalable parallel algorithms and simplifies their analysis. The model rests on the novel idea of...
A Work-Optimal Algorithm on log delta n Processors for a P-Complete Problem (2001)
Gustedt, Jens, Arne Telle, Jan
We present a parallel algorithm for the Lexicographically First Maximal Independent Set Problem on graphs with bounded degree 3 that is work-optimal on a shared memory machine with up to $\log...
The Treewidth of Java Programs (2001)
Gustedt, Jens, Maehle, Ole A., Telle, Jan Arne
Intuitively, the treewidth of a graph $G$ measures how close $G$ is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on $G$, by dynamic programming...
PRO: a model for Parallel Resource-Optimal Computation (2001)
Gebremedhin, Assefaw Hadish, Gustedt, Jens, Guérin Lassous, Isabelle, Telle, Jan Arne
We present a new parallel computational model that enables the design of resource-optimal scalable parallel algorithms and simplifies their analysis. The model rests on the novel idea of...
A Work-Optimal Algorithm on log delta n Processors for a P-Complete Problem (2001)
Gustedt, Jens, Arne Telle, Jan
We present a parallel algorithm for the Lexicographically First Maximal Independent Set Problem on graphs with bounded degree 3 that is work-optimal on a shared memory machine with up to $\log...
A Work-Optimal Algorithm on log delta n Processors for a P-Complete Problem (2001)
Gustedt, Jens, Arne Telle, Jan
We present a parallel algorithm for the Lexicographically First Maximal Independent Set Problem on graphs with bounded degree 3 that is work-optimal on a shared memory machine with up to $\log...
The Treewidth of Java Programs (2001)
Gustedt, Jens, Maehle, Ole A., Telle, Jan Arne
Intuitively, the treewidth of a graph $G$ measures how close $G$ is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on $G$, by dynamic programming...
PRO: a model for Parallel Resource-Optimal Computation (2001)
Gebremedhin, Assefaw Hadish, Gustedt, Jens, Guérin Lassous, Isabelle, Telle, Jan Arne
We present a new parallel computational model that enables the design of resource-optimal scalable parallel algorithms and simplifies their analysis. The model rests on the novel idea of...
Communication and Memory Optimized Tree Contraction and List Ranking (2000)
We present a simple and efficient algorithm for the Tree Contraction Problem on a Coarse Grained $p$-Multiprocessor. With respect to its total computing time, its demand of memory and its total...
The Handling of Graphs on PC Clusters : A Coarse Grained Approach (2000)
Guérin Lassous, Isabelle, Gustedt, Jens, Morvan, Michel
We study the relationship between the design and analysis of graph algorithms in the coarsed grained parallel models and the behavior of the resulting code on clusters. We conclude that the coarse...
Graph Coloring on a Coarse Grained Multiprocessor (extended abstract) (2000)
Gebremedhin, Assefaw Hadish, Guérin Lassous, Isabelle, Gustedt, Jens, Telle, Jan Arne
We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph $G$ with a guarantee of at most $\D +1$ colors.
Java Programs do not have bounded treewidth (2000)
Gustedt, Jens, Maehle, Ole, Telle, Jan Arne
We show that the control flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing k labels and a loop...
Guérin Lassous, Isabelle, Gustedt, Jens, Morvan, Michel
We study the relationship between the design and analysis of graph algorithms in the coarsed grained parallel models and the behavior of the resulting code on todays parallel machines and clusters....
List Ranking on PC Clusters (2000)
Guérin Lassous, Isabelle, Gustedt, Jens
We present two algorithms for the List Ranking Problem in the Coarse Grained Multicomputer model (CGM for short): if $p$ is the number of processors and $n$ the size of the list, then we give a...
Java Programs do not have Bounded Treewidth (2000)
Gustedt, Jens, Mæhle, Ole A., Telle, Jan Arne
We show that the control-flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing $k$ labels and a loop...
Java Programs do not have bounded treewidth (2000)
Gustedt, Jens, Maehle, Ole, Telle, Jan Arne
We show that the control flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing k labels and a loop...
Communication and Memory Optimized Tree Contraction and List Ranking (2000)
We present a simple and efficient algorithm for the Tree Contraction Problem on a Coarse Grained $p$-Multiprocessor. With respect to its total computing time, its demand of memory and its total...
The Handling of Graphs on PC Clusters : A Coarse Grained Approach (2000)
Guérin Lassous, Isabelle, Gustedt, Jens, Morvan, Michel
We study the relationship between the design and analysis of graph algorithms in the coarsed grained parallel models and the behavior of the resulting code on clusters. We conclude that the coarse...
Graph Coloring on a Coarse Grained Multiprocessor (extended abstract) (2000)
Gebremedhin, Assefaw Hadish, Guérin Lassous, Isabelle, Gustedt, Jens, Telle, Jan Arne
We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph $G$ with a guarantee of at most $\D +1$ colors.
Guérin Lassous, Isabelle, Gustedt, Jens, Morvan, Michel
We study the relationship between the design and analysis of graph algorithms in the coarsed grained parallel models and the behavior of the resulting code on todays parallel machines and clusters....
List Ranking on PC Clusters (2000)
Guérin Lassous, Isabelle, Gustedt, Jens
We present two algorithms for the List Ranking Problem in the Coarse Grained Multicomputer model (CGM for short): if $p$ is the number of processors and $n$ the size of the list, then we give a...
Java Programs do not have Bounded Treewidth (2000)
Gustedt, Jens, Mæhle, Ole A., Telle, Jan Arne
We show that the control-flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing $k$ labels and a loop...
The Handling of Graphs on PC Clusters : A Coarse Grained Approach (2000)
Guérin Lassous, Isabelle, Gustedt, Jens, Morvan, Michel
We study the relationship between the design and analysis of graph algorithms in the coarsed grained parallel models and the behavior of the resulting code on clusters. We conclude that the coarse...
List Ranking on PC Clusters (2000)
Guérin Lassous, Isabelle, Gustedt, Jens
We present two algorithms for the List Ranking Problem in the Coarse Grained Multicomputer model (CGM for short): if $p$ is the number of processors and $n$ the size of the list, then we give a...
Java Programs do not have Bounded Treewidth (2000)
Gustedt, Jens, Mæhle, Ole A., Telle, Jan Arne
We show that the control-flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing $k$ labels and a loop...
Guérin Lassous, Isabelle, Gustedt, Jens, Morvan, Michel
We study the relationship between the design and analysis of graph algorithms in the coarsed grained parallel models and the behavior of the resulting code on todays parallel machines and clusters....
Graph Coloring on a Coarse Grained Multiprocessor (extended abstract) (2000)
Gebremedhin, Assefaw Hadish, Guérin Lassous, Isabelle, Gustedt, Jens, Telle, Jan Arne
We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph $G$ with a guarantee of at most $\D +1$ colors.
Communication and Memory Optimized Tree Contraction and List Ranking (2000)
We present a simple and efficient algorithm for the Tree Contraction Problem on a Coarse Grained $p$-Multiprocessor. With respect to its total computing time, its demand of memory and its total...
Java Programs do not have bounded treewidth (2000)
Gustedt, Jens, Maehle, Ole, Telle, Jan Arne
We show that the control flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing k labels and a loop...
Java Programs do not have bounded treewidth (2000)
Gustedt, Jens, Maehle, Ole, Telle, Jan Arne
We show that the control flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing k labels and a loop...
Graph Coloring on a Coarse Grained Multiprocessor (2000)
Assefaw Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle
. We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph G with a guarantee of at most D G +1 colors. 1 Introduction and Overview The problem of graph...
Graph coloring on a coarse grained multiprocessor (2000)
Assefaw Hadish Gebremedhin, Isabelle Guérin Lassous, Jens Gustedt, Jan Arne Telle
Abstract. We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph G with a guarantee of at most ΔG £ 1 colors. 1 Introduction and Overview The problem of...
Java Programs do not have bounded treewidth (2000)
Gustedt, Jens, Maehle, Ole, Telle, Jan Arne
We show that the control flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method containing k labels and a loop...
Partially Complemented Representations of Digraphs (1999)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalen- ce relation where two digraphs are equivalent...
Efficient and Practical Algorithms for Sequential Modular Decomposition (1999)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A module of an undirected graph G=(V,E) is a set X of vertices that have the same set of neighbors in V \ X. The modular decomposition is a unique decomposition of the vertices into nested modules....
List Ranking on a Coarse Grained Multiprocessor (1999)
Guérin Lassous, Isabelle, Gustedt, Jens
We present a deterministic algorithm for the List Ranking Problem on a Coarse Grained p-Multiprocessor (CGM) that is only a factor of log*(p) away from optimality. This statement holds as well for...
Partially Complemented Representations of Digraphs (1999)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalen- ce relation where two digraphs are equivalent...
Efficient and Practical Algorithms for Sequential Modular Decomposition (1999)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A module of an undirected graph G=(V,E) is a set X of vertices that have the same set of neighbors in V \ X. The modular decomposition is a unique decomposition of the vertices into nested modules....
List Ranking on a Coarse Grained Multiprocessor (1999)
Guérin Lassous, Isabelle, Gustedt, Jens
We present a deterministic algorithm for the List Ranking Problem on a Coarse Grained p-Multiprocessor (CGM) that is only a factor of log*(p) away from optimality. This statement holds as well for...
List Ranking on a Coarse Grained Multiprocessor (1999)
Guérin Lassous, Isabelle, Gustedt, Jens
We present a deterministic algorithm for the List Ranking Problem on a Coarse Grained p-Multiprocessor (CGM) that is only a factor of log*(p) away from optimality. This statement holds as well for...
Efficient and Practical Algorithms for Sequential Modular Decomposition (1999)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A module of an undirected graph G=(V,E) is a set X of vertices that have the same set of neighbors in V \ X. The modular decomposition is a unique decomposition of the vertices into nested modules....
Partially Complemented Representations of Digraphs (1999)
Dahlhaus, Elias, Gustedt, Jens, Mcconnell, Ross M.
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalen- ce relation where two digraphs are equivalent...
Partially Complemented Representations of (1999)
Elias Dahlhaus, Jens Gustedt, Ross M. Mcconnell
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent...
Efficient and practical algorithms for sequential modular decomposition (1999)
Elias Dahlhaus, Jens Gustedt, Ross M. McConnell
A module of an undirected graph G = (V, E) is a set X of vertices that have the same set of neighbors in V \ X. The modular decomposition is a unique decomposition of the vertices into nested...
List Ranking on a Coarse Grained Multiprocessor (1999)
Isabelle Guérin Lassous, Isabelle Gurin Lassous, Jens Gustedt, Jens Gustedt, Projet Rsdas
: We present a deterministic algorithm for the List Ranking Problem on a Coarse Grained p- Multiprocessor (CGM) that is only a factor of log (p) away from optimality. This statement holds as well for...
Linear-time register allocation for a fixed number of registers (1998)
Hans Bodlaender, Jens Gustedt, Jan Arne Telle
Abstract We show that for any fixed number of registers there is a linear-time algorithm which given a structured (j goto-free) program finds, if possible, an allocation of variables to registers...
Finiteness Theorems for Graphs and Posets Obtained by Compositions (1998)
We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that...
How to format a submission for DMTCS with the journal's own LaTeX2e-style (1998)
this document in its pdf form you may see some of the advantages this has: in particular pdf documents produced in that way have included hyperlinks. If you want to know more about these features...
Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices (1998)
Stefan Felsner, Stefan Felsner, Jens Gustedt, Jens Gustedt, Michel Morvan, Michel Morvan
. We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P . Two bijections of this type have been...
Weak-order extensions of an order (1997)
Karell Bertet, Karell Bertet, Jens Gustedt, Jens Gustedt, Michel Morvan, Michel Morvan
gustedt@math.tu-berlin.de. Supported by IFP Digitale Filter. Abstract In this paper, at first we describe a graph representing all the weak-order extensions of a partially ordered set and an...
Efficient and Practical Modular Decomposition (1997)
Elias Dahlhaus Jens, Jens Gustedt, Ross M. Mcconnell
We give a simple recursive algorithm for modular decomposition of undirected graphs that runs in O(n+ma(m;n)) time. Previous algorithms with this bound are of theoretical use only. By adding some...
Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel (1997)
. For each minor-closed graph class we show that a simple variant of Boruvka's algorithm computes a MST for any input graph belonging to that class with linear costs. Among minor-closed graph...
Linear-Time Register Allocation for a Fixed Number of Registers (1997)
Hans Bodlaender, Hans Bodlaender, Jens Gustedt, Jens Gustedt, Jan Arne Telle
We show that for any fixed number of registers there is a linear-time algorithm which given a structured (j goto-free) program finds, if possible, an allocation of variables to registers without...
A Compact Data Structure and Parallel Algorithms for Permutation Graphs (1995)
Jens Gustedt, Jens Gustedt, Michel Morvan, Michel Morvan, Laurent Viennot, ...
. Starting from a permutation of f0; : : : ; n \Gamma 1g we compute in parallel with a workload of O(n log n) a compact data structure of size O(n log n). This data structure allows to obtain the...
A Compact Data Structure and Parallel Algorithms for Permutation Graphs (1995)
Jens Gustedt, Michel Morvan, Laurent Viennot, Paris Denis Diderot
. Starting from a permutation of f0; : : : ; n \Gamma 1g we compute in parallel with a workload of O(n log n) a compact data structure of size O(n log n). This data structure allows to obtain the...
Testing Hereditary Properties Efficiently on Average (1994)
Angelika Steger, Jens Gustedt, Jens Gustedt
. We use the quasi-ordering of substructure relations such as induced and weak subgraph, induced suborder, graph minor or subformula of a CNF formula to obtain recognition algorithms for hereditary...
Algorithmic aspects of ordered structures. (1992)
Mikroreprod. eines Ms. IV, 79 Bl. : graph. Darst.
Graph Coloring on a Coarse Grained Multiprocessor
Assefaw Hadish Gebremedhin, Isabelle Guerin Lassous, Jens Gustedt, Jan Arne Telle
We present the first efficient algorithm for a coarse grained multiprocessor that colors a graph with a guarantee of at most D G +1 colors. 1 Introduction and Overview The problem of graph coloring...