David Semé

chapter

An Efficient Sequence Alignment Algorithm on a LARPBS

David Semé, Sidney Youlou

Lecture Notes in Computer Science > Computational Science and Its Applications – ICCSA 2007 > General Track > 379-387

In this paper, we give a parallel algorithm solving the sequence alignment problem on a LARPBS, one of the recently proposed parallel model based on optical bus. The complexity of our algorithm solving the sequence alignment problem is O(m) using n processors (where m and n are respectively the sizes of the shortest and the longest sequences).

chapter

A CGM Algorithm Solving the Longest Increasing Subsequence Problem

David Semé

Lecture Notes in Computer Science > Computational Science and Its Applications - ICCSA 2006 > Workshop on Parallel and Distributed Computing (PDC 2006) > 10-21

In this paper, we consider parallel algorithm for the longest increasing subsequence problem. Although this problem is primitive combinatorial optimization problem, this is not known to be in the class NC or P-complete, that is, no NC algorithm have been proposed for this problem, and there is no proof which shows the problem is P-complete. We present a coarse grained parallel algorithm that solves...

chapter

A Coarse-Grained Multicomputer Algorithm for the Longest Repeated Suffix Ending at Each Point in a Word

Thierry Garcia, David Semé

Lecture Notes in Computer Science > Computational Science and Its Applications — ICCSA 2003 > Coarse Grained Parallel Algorithms for Scientific Applications > 239-248

The paper presents a Coarse-Grained Multicomputer algorithm that solves the problem of finding the longest repeated suffix ending at each point in a word. This algorithm can be implemented in the CGM with P processors in $$ O\left( {\frac{{N^2 }} {P}} \right) $$ in time and O(P) communication steps. It is the first CGM algorithm for this problem. We present also experimental results showing that...

article

Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory

Jean-Frédéric Myoupo, David Semé

The Journal of Supercomputing > 2006 > 38 > 1 > 83-107

This paper presents BSR-parallel algorithms for some problems in fundamental graph theory : transitive closure, connected components, spanning tree, bridges and articulation points of a graph and bipartite graph recognition. There already exist constant time algorithms to solve these problems on a mesh with reconfigurable bus system using O(N ⁴) processors. Here we show that these problems...

article

A Coarse-Grained Multicomputer algorithm for the detection of repetitions

Thierry Garcia, David Semé

Information Processing Letters > 2005 > 93 > 6 > 307-313

The paper presents a Coarse-Grained Multicomputer algorithm that solves the problem of detection of repetitions. This algorithm can be implemented in the CGM model with P processors in O(N2P) in time and O(P) communication steps. It is the first CGM algorithm for this problem. We present also experimental results showing that the CGM algorithm is very efficient.

article

Optimal BSR Solutions to Several Convex Polygon Problems

Jean-Frédéric Myoupo, David Semé, Ivan Stojmenovic

The Journal of Supercomputing > 2002 > 21 > 1 > 77-90

This paper focuses on BSR (Broadcasting with Selective Reduction) implementation of algorithms solving basic convex polygon problems. More precisely, constant time solutions on a linear number, max(N, M) (where N and M are the number of edges of the two considered polygons), of processors for computing the maximum distance between two convex polygons, finding critical support lines of two convex polygons,...

article

Time-Efficient Parallel Algorithms for the Longest Common Subsequence and Related Problems

Jean-Frédéric Myoupo, David Semé

Journal of Parallel and Distributed Computing > 1999 > 57 > 2 > 212-223

Recently Aklet al. introduced a new model of parallel computation, called broadcasting with selective reduction (BSR), and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for implementation than even EREW PRAM. The model allows constant time solutions to sorting, parallel prefix, and other problems. In this paper, we describe constant time solutions to the longest...

INFONA - science communication portal

Search results for: David Semé

An Efficient Sequence Alignment Algorithm on a LARPBS

A CGM Algorithm Solving the Longest Increasing Subsequence Problem

A Coarse-Grained Multicomputer Algorithm for the Longest Repeated Suffix Ending at Each Point in a Word

Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory

A Coarse-Grained Multicomputer algorithm for the detection of repetitions

Optimal BSR Solutions to Several Convex Polygon Problems

Time-Efficient Parallel Algorithms for the Longest Common Subsequence and Related Problems

Filter options

Publication date

Publication type

Keywords

Data set

Journal

INFONA - science communication portal

Search results for: David Semé

An Efficient Sequence Alignment Algorithm on a LARPBS

A CGM Algorithm Solving the Longest Increasing Subsequence Problem

A Coarse-Grained Multicomputer Algorithm for the Longest Repeated Suffix Ending at Each Point in a Word

Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory

A Coarse-Grained Multicomputer algorithm for the detection of repetitions

Optimal BSR Solutions to Several Convex Polygon Problems

Time-Efficient Parallel Algorithms for the Longest Common Subsequence and Related Problems

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Publication type

Keywords

Data set

Journal

Reporting an error / abuse

Sending the report failed

Accessibility options