Person

François Margot

This person is no longer with EPFL

Related publications (11)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

A catalog of minimally nonideal matrices

François Margot

This paper describes a backtracking algorithm for the enumeration of nonisomorphic minimally nonideal (n2n) matrices that are not degenerate projective planes. The application of this algorithm for nh12 yielded 20 such matrices, adding 5 matrices to the 15 ...

1998

Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron

Thomas Liebling, François Margot

In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack ...

1997

Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results

Thomas Liebling, François Margot

We present an O(p*n) algorithm for the problem of finding disjoint simple paths of minimum total length between p given pairs of terminals on oriented partial 2-trees with n nodes and positive or negative arc lengths. The algorithm is in O(n) if all termin ...

1995

Some complexity results about threshold graphs

François Margot

The problem of determining whether a graph G contains a threshold subgraph containing at least h edges is shown to be NP-complete if h is part of the input as the problems of minimum threshold completion, weighted 2-threshold partition and weighted 2-thres ...

1994

Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron

Thomas Liebling, François Margot

In this paper, we investigate the applicability of backtrack technique for solving the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtra ...

1994

Tree polytope on 2-trees

Thomas Liebling, François Margot

We give a complete polyhedral characterization of the tree polytope (convex hull of the characteristic vectors of trees in the graph) on 2-trees. ...

1994

Routages et heuristiques

Thomas Liebling, François Margot

Le routage est un problème-clé dans la conception et l'eploitation des systèmes techniques et industriels les plus divers. Il en est ainsi pour la construction de réseaux de dsitribution - élextricité, eau, etc.-, le câblage de circuits VLSI ou encore la p ...

1989

The poset scheduling problem

Thomas Liebling, François Margot

The poser scheduling problem has been shown to be NP-complete in the general case but in P for a special case by Chang and Edmonds. In this paper, we extend the class of polynomially solvable cases and give some polyhedral characterizations. ...

1989

A note on order preserving matchings

Thomas Liebling, François Margot

We study order preserving injections or bipartite matchings from poset V1 to poset V2. When V1 is totally ordered, we give an efficient algorithm for the associated optimization problem and the convex hull of the corresponding characteristic vectors. If V2 ...

1989

Node disjoint paths of minimum total lenght on 2-trees

Thomas Liebling, François Margot

The problem of finding p(and even 2) node disjoint paths on a digraph, connecting p pair of terminals is NP-complete. For directed k-trees however, the problem is polynomial. In this paper, we give a linear algorithm for the corresponding optimisation prob ...

1988