-
Identifying codes in line graphs
International audience -
Complexity of Task Graph Scheduling with Fixed Communication Capacity
Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be modeled by a task graph, where vertices represent tasks and... -
The Synthesis Problem for Elementary Net Systems is NP-Complete
The so-called synthesis problem consists in deciding for a class of nets whether a given graph is isomorphic to the case graph of some net and then constructing the... -
Scheduling of Parallel Programs in Single-Bus Multiprocessor Systems
Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be represented by a task graph, where vertices represent tasks... -
Detection number of bipartite graphs and cubic graphs
For a connected graph G of order |V(G)| ≥ 3 and a k-labelling c : E(G) → {1,2, . . . ,k} of the edges of G, the code of a vertex v of G is the ordered k-tuple (ℓ1, ℓ2,... -
Algorithmic aspects of graph colourings heuristics
A proper colouring of a graph is a function that assigns a colour to each vertex with the restriction that adjacent vertices are assigned with distinct colours. Proper... -
Combinatorial and algorithmic aspects of identifying codes in graphs
We study combinatorial and algorithmic aspects of identifying codes in graphs. An identifying code is a set of vertices of a graph such that, on the one hand, each... -
Minimization of the receiver cost in an all-optical ring with a limited numbe...
International audience -
NP-Completeness of ad hoc multicast routing problems
In this research report, we study the algorithmic complexity of different broadcast and multicast ad hoc routing problems given a wireless medium. -
A Family of Fast Syndrome Based Cryptographic Hash Functions
Recently, some collisions have been exposed for a variety of cryptographic hash functions including some of the most widely used today. Many other hash functions using... -
Strong edge-colouring and induced matchings
International audience -
Towards automatic recovery in protocol-based Web service composition
In a protocol-based Web service composition, a set of available component services collaborate together in order to provide a new composite service. Services export... -
Vertex Partitions of Graphs into Cographs and Stars
International audience -
Decision and approximation complexity for identifying codes and locating-domi...
International audience -
Quantum Secret Sharing with Graph States
Revised Selected Papers - http://www.memics.cz/2012/ -
NP-Completeness Results for Minimum Planar Spanners
International audience -
P_4-Colorings and P_4-Bipartite Graphs
International audience -
New Results on Generalized Graph Coloring
International audience -
Computational Complexity of Simultaneous Elementary Matching Problems
Article dans revue scientifique avec comité de lecture.
