Source author record

Emeric Gioan

Emeric Gioan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms math.CO

Catalog footprint

What is connected

5works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices

Provided n points in an (n-1)-dimensional affine space, and one ordering of the points for each coordinate, we address the problem of testing whether these orderings determine if the points are the vertices of a simplex (i.e. are affinely independent), regardless of the real values of the coordinates. We also attempt to determine the orientation of this simplex. In other words, given a matrix whose columns correspond to affine points, we want to know when the sign (or the non-nullity) of its determinant is implied by orderings given to each row for the values of the row. We completely solve the problem in dimensions 2 and 3. We provide a direct combinatorial characterization, along with a formal calculus method. It can also be viewed as a decision algorithm, and is based on testing the existence of a suitable inductive cofactor expansion of the determinant. We conjecture that our method generalizes in higher dimensions. This work aims to be part of a study on how oriented matroids encode shapes of 3-dimensional landmark-based objects. Specifically, applications include the analysis of anatomical data for physical anthropology and clinical research.

preprint2014arXiv

Computation with No Memory, and Rearrangeable Multicast Networks

We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one component at a time, hence using no memory. In this paper, we survey this problem introduced in previous papers by the authors, we detail its close relation with rearrangeable multicast networks, and we provide new results for both viewpoints. A bijective mapping can be computed by 2n - 1 component modifications, that is by a program of length 2n - 1, a result equivalent to the rearrangeability of the concatenation of two reversed butterfly networks. For a general arbitrary mapping, we give two methods to build a program with maximal length 4n-3. Equivalently, this yields rearrangeable multicast routing methods for the network formed by four successive butterflies with alternating reversions. The first method is available for any set S and practically equivalent to a known method in network theory. The second method, a refinement of the first, described when |S| is a power of 2, is new and allows more flexibility than the known method. For a linear mapping, when S is any field, or a quotient of an Euclidean domain (e.g. Z/sZ for any integer s), we build a program with maximal length 2n - 1. In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint, and giving moreover directly a program for the inverse when it exists. This yields also a new result on matrix decompositions, and a new result on the multicast properties of two successive reversed butterflies. Results of this flavour were known only for the boolean field Z/2Z.

preprint2012arXiv

Practical and Efficient Circle Graph Recognition

Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is O(n + m) times the inverse Ackermann function, α(n + m), whose value is smaller than 4 for any practical graph. The algorithm is based on a new incremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The algorithm is an extension of a Split Decomposition algorithm with the same running time developed by the authors in a companion paper.

preprint2012arXiv

Practical and Efficient Split Decomposition via Graph-Labelled Trees

Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decomposition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time $O(n+m)α(n+m)$, where $α$ is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus' linear-time split decomposition algorithm [Dahlhaus'00], which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation details are given in this paper. Also, our algorithm extends to circle graph recognition, whereas no such extension is known for Dahlhaus' algorithm. The companion paper [Gioan et al.] uses our algorithm to derive the first sub-quadratic circle graph recognition algorithm.

preprint2011arXiv

Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs

In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give strutural and incremental characterizations, leading to optimal fully-dynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on a new framework to represent the split decomposition, namely the graph-labelled trees, which also captures the modular decomposition of graphs and thereby unify these two decompositions techniques. The point of the paper is to use bijections between these graph classes and trees whose nodes are labelled by cliques and stars. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.