Search

Your search keyword '"Paul, Christophe"' showing total 34 results
Start Over Author "Paul, Christophe" Publisher hal ccsd
34 results on '"Paul, Christophe"'

1. Special Issue Dedicated to the 13th International Symposium on Parameterized and Exact Computation

Author

Paul, Christophe, Pilipczuk, Michał, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), and University of Warsaw (UW)

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; This special issue of Algorithmica to the 13th International Symposium on Parameterized and Exact Computation (IPEC) held in Helsinki, Finland. IPEC (formerly IWPEC) is a series of international symposia covering research in all aspects of parameterized and exact algorithms and complexity. Started in 2004 as a biennial workshop, it became an annual event in 2009 and is now a highly recognized annual meeting. This special issue is a successor of following special issue volumes of Algorithmica: volumes 64(1)-2012 and 65(4)-2013 dedicated to IPEC 2010, held in Chennai (India); volume 71(3)-2015 dedicated to IPEC 2013, held in Sophia Antipolis (France); volume 75(2)-2016 dedicated to IPEC 2014, held in Wrocław (Poland); volume 79(1)-2017 dedicated to IPEC 2015, held in Patras (Greece); volume 81(2)-2019 dedicated to IPEC 2016, held in Aarhus (Denmark); volume 81(10)-2019 dedicated to IPEC 2017, held in Vienna (Austria).

Published
2020

2. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Author

Paul, Christophe, Bläser, Markus, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Universität des Saarlandes [Saarbrücken], Christophe Paul, and Markus Bläser

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Abstract

International audience; The 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) will be held in Montpellier, March 10 — 13, 2020. It is organized by the LIRMM (Université de Montpellier, CNRS) and will be hosted by Polytech' Montpellier on the Triolet Compus of Montpellier University.

Published
2020

3. Connected tree-width and connected cops and robber game

Author

Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2019

4. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019): March 13-16, 2019, Berlin, Germany

Author

Niedermeier, Rolf, Paul, Christophe, Technische Universität Berlin (TU), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Abstract

International audience; Front Matter, Table of Contents, Preface, Conference Organization

Published
2019

5. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Author

Paul, Christophe, Pilipczuk, Michal, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), and University of Warsaw (UW)

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; Front Matter, Table of Contents, Preface, Conference Organization

Published
2019

6. A polynomial Turing kernel to compute the cut-width of semi-complete digraph

Author

Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2018

7. Preface: Seventh Workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, October 2015

Author

Corneil, Derek, Oum, Sang-Il, Paul, Christophe, Department of Computer Science [University of Toronto] (DCS), University of Toronto, Department of Mathematical Sciences, KAIST, KAIST, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2018

8. Introduction to parameterized complexity and some algorithmic consequences of the graph minor theory

Author

Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2015

9. A single-exponential FPT algorithm for the $K_4$-minor cover problem

Author

Kim, Eun Jung, Paul, Christophe, Philip, Geevarghese, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Institute of Mathematical Sciences [Chennai] (IMSc), ANR: AGAPE,AGAPE,Algorithmes de Graphes à Paramètre fixe et Exponentiels exacts(2009), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, and ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009)

Subjects
FOS: Computer and information sciences, Computer Science - Computational Complexity, Discrete Mathematics (cs.DM), Computer Science::Discrete Mathematics, Computer Science - Data Structures and Algorithms, Vertex Cover, [INFO]Computer Science [cs], Data Structures and Algorithms (cs.DS), FPT time, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS, Computer Science - Discrete Mathematics
Abstract

Given an input graph G and an integer k, the parameterized K_4-minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K_4-minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can also be expressed as Treewidth-t Vertex Deletion problems: t=0 for Vertex Cover and t=1 for Feedback Vertex Set. While a single-exponential FPT algorithm has been known for a long time for \textsc{Vertex Cover}, such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth-t Vertex Deletion can be solved in time c^{o(k)}.n^{O(1)}, it was open whether the K_4-minor cover problem could be solved in single-exponential FPT time, i.e. in c^k.n^{O(1)} time. This paper answers this question in the affirmative.

Published
2015

10. FPT Algorithm and Polynomial Kernel for Linear Rank-width One Vertex Deletion

Author

Kanté, Mamadou Moustapha, Kim, Eun, Kwon, O-joung, Paul, Christophe, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Published
2015

11. Split decomposition, circle graphs and related graph families

Author

Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and Ming-Yang Kao

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2015

12. Algorithmics of Modular Decomposition

Author

Paul, Christophe, Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; We propose a review of algorithms to compute the modular decomposition of a graph as well as various algorithmic application of modular decomposition.

Published
2012

13. On the (Non-)Existence of Polynomial Kernels for Pl -Free Edge Modification Problems

Author

Guillemot, Sylvain, Paul, Christophe, Perez, Anthony, Paul, Christophe, Lehrstuhl Bioinformatik Jena, Friedrich-Schiller-Universität = Friedrich Schiller University Jena [Jena, Germany], Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; Given a graph G = (V , E) and an integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set of edges F of size at most k such that the graph H = (V , E △ F ) satisfies the property Π. In the Π edge-completion problem, the set F of edges is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-edition problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size k of the edge set F , It has been proved that (Cai, IPL:58(4)-1996) if Π is an hereditary property characterized by a finite set of forbidden induced subgraph, then the three Π edge-modification problems are fixed-parameter tractable. It was then natural to ask (Cai, IWPEC 2006) whether these Π edge-modification problems also admit a polynomial size kernel (i.e. any instance (G, k) can be reduced in polynomial time to an equivalent instance (G′ , k′ ) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlstr¨om (IWPEC 2009) answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraph. It is a challenging question to characterized for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlstr¨om asked whether the result holds when the forbidden subgraphs are paths and pointed out that the problem is already open in the case of P4 -free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for Pl -free graphs and Cl -free graph for large enough l.

Published
2010

14. Recognition of dynamic circle graphs

Author

Crespelle, Christophe, Gioan, Emeric, Paul, Christophe, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2014

15. Complexité et algorithmes paramétrés

Author

Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Philippe Langlois, and ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

National audience

Published
2013

16. Parameterized K_4-Cover in Single Exponential Time

Author

Kim, Eunjung, Paul, Christophe, Philip, Geevarghese, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and Institute of Mathematical Sciences [Chennai] (IMSc)

Subjects
Computer Science::Discrete Mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; Given an input graph G on n vertices and an integer k, the parameterized K4-minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K4-minor free graph or, equivalently, in a graph of treewidth at most 2. The problem can thus also be called Treewidth-2 Vertex Deletion. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can be expressed as Treewidth-t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set. While a single-exponential FPT algorithm has been known for a long time for Vertex Cover, such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth-t Vertex Deletion can be solved in time $c^{o(k)} * n^{O(1)}$, it was open whether the K4-minor cover could be solved in single-exponential FPT time, i.e. in $c^k * n^{O(1)}$ time. This paper answers this question in the affirmative

Published
2012

17. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs

Author

Crespelle, Christophe, Paul, Christophe, Dynamic Networks (DNET), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs.

Published
2010

18. On the Approximability Results for Maximum Agreement Subtree and Maximum Compatible Tree Problems

Author

Nicolas, François, Guillemot, Sylvain, Berry, Vincent, Paul, Christophe, Méthodes et Algorithmes pour la Bioinformatique (MAB), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and Algorithmes, Graphes et Combinatoire (ALGCO)

Subjects
Complement problem, Minimum dominating set, Maximum compatible tree, Consensus tree, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Approximation algorithm, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Maximum agreement subtree, Computational biology, Phylogenetics, Approximation hardness, Maximum refinement subtree, Maximum independent set, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Maximum star-forest
Abstract

International audience; The aim of this paper is to give a complete picture of approximability for two tree consensus problems which are of particular interest in computational biology: Maximum Agreement SubTree (MAST) and Maximum Compatible Tree (MCT). Both problems take as input a label set and a collection of trees whose leaf sets are each bijectively labeled with the label set. Define the size of a tree as the number of its leaves. The well-known MAST problem consists of finding a maximum-sized tree that is topologically embedded in each input tree, under label-preserving embeddings. Its variant MCT is less stringent, as it allows the input trees to be arbitrarily refined. Our results are as follows. We show that MCT is -hard to approximate within bound n1− on rooted trees, where n denotes the size of each input tree; the same approximation lower bound was already known for MAST [J. Jansson, Consensus algorithms for trees and strings, Ph. D. Thesis, Lund University, 2003]. Furthermore, we prove that MCT on two rooted trees is not approximable within bound 2log1−n, unless all problems in are solvable in quasi-polynomial time; the same result was previously established for MAST on three rooted trees [J. Hein, T. Jiang, L. Wang, K. Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics 71 (1-3) (1996) 153-169] (note that MAST on two trees is solvable in polynomial time [M.A. Steel, T.J. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtree, Information Processing Letters 48 (2) (1993) 77-82]). Let CMAST, resp. CMCT, denote the complement version of MAST, resp. MCT: CMAST, resp. CMCT, consists of finding a tree that is a feasible solution of MAST, resp. MCT, and whose leaf label set excludes a smallest subset of the input labels. The approximation threshold for CMAST, resp. CMCT, on rooted trees is shown to be the same as the approximation threshold for CMAST, resp. CMCT, on unrooted trees; it was already known that both CMAST and CMCT are approximable within ratio three on rooted and unrooted trees [V. Berry, F. Nicolas, Maximum agreement and compatible supertrees, in: S.C. Sahinalp, S. Muthukrishnan, U. Dogrusoz (Eds.), Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM'04, in: LNCS, vol. 3109, Springer-Verlag, 2004, pp. 205-219; G. Ganapathy, T.J. Warnow, Approximating the complement of the maximum compatible subset of leaves of k trees, in: K. Jansen, S. Leonardi, V. V. Vazirani (Eds.), Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX'02, in: LNCS, vol. 2462, Springer-Verlag, 2002, pp. 122-134]. The latter results are completed by showing that CMAST is -hard on three rooted trees and that CMCT is -hard on two rooted trees.

Published
2009

19. Kinetic Maintenance of Mobile k-Centres in Trees

Author

Paul, Christophe, Durocher, Stéphane, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; Given a set P of points (clients) on a weighted tree T , a k-centre of P corresponds to a set of k points (facilities) on T such that the maximum graph distance between any client and its nearest facility is minimized. We consider the mobile k-centre problem on trees. Let C denote a set of n mobile clients, each of which follows a continuous tra jectory on a weighted tree T . We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of C . When each client in C moves with linear motion along a path on T , the motions of the corresponding 1-centre and 2-centre are piecewise linear; we derive a tight combinatorial bound of Θ(n) on the complexity of the motion of the 1-centre and corresponding bounds of O(n^2 α(n)) and Ω(n^2 ) for a 2-centre, where α(n) denotes the inverse Ackermann function. We describe efficient algorithms for calculating the tra jectories of the 1-centre and 2-centre of C : the 1-centre can be found in optimal time O(n log n) and a 2-centre can be found in time O(n^2 log n). These algorithms lend themselves to implementation within the framework of kinetic data structures. Finally, we examine properties of the mobile 1-centre on graphs and describe an optimal unit-velocity 2-approximation.

Published
2009

20. Algorithmic Generation of Graphs of Branch-width ≤ k

Author

Paul, Christophe, Proskurowski, Andrzej, Telle, Jan Arne, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Computer Science Department [Oregon], University of Oregon [Eugene], Department of Informatics [Bergen] (UiB), and University of Bergen (UiB)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; Branchwidth is a connectivity parameter of graphs closely related to treewidth. Graphs of treewidth at most k can be generated algorithmically as the subgraphs of k-trees. In this paper, we investigate the family of edge-maximal graphs of branchwidth k, that we call k-branches. The k-branches are, just as the k-trees, a subclass of the chordal graphs where all minimal separators have size k. However, a striking difference arises when considering subgraph-minimal members of the family. Whereas K_{k+1} is the only subgraph-minimal k-tree, we show that for any k ≤ 7 a minimal k-branch having q maximal cliques exists for any value of q different than 3 and 5, except for k=8,q=2. We characterize subgraph-minimal k-branches for all values of k. Our investigation leads to a generation algorithm, that adds one or two new maximal cliques in each step, producing exactly the k-branches.

Published
2008

21. Interval completion is Fixed Parameter Tractable

Author

Paul, Christophe, Telle, Jan Arne, Villanger, Yngve, Heggerness, Pinar, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Department of Informatics [Bergen] (UiB), University of Bergen (UiB), and Lirmm

Subjects
Fixed Parametrized Algorithms, Interval graphs, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We present an algorithm with runtime $O(k^{2k}n^3m)$ for the following NP-complete problem: Given an arbitrary graph $G$ on $n$ vertices and $m$ edges, can we obtain an interval graph by adding at most $k$ new edges to $G$? This resolves the long-standing open question, first posed by Kaplan, Shamir and Tarjan, of whether this problem could be solved in time $f(k).n^{O(1)}$. The problem has applications in Physical Mapping of DNA and in Profile Minimization for Sparse Matrix Computations. For the first application, our results show tractability for the case of a small number $k$ of false negative errors, and for the second, a small number $k$ of zero elements in the envelope. Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph, and combines this with a greedy algorithm when graphs of a certain structure are reached by the search. The presented result is surprising, as it was not believed that a bounded search tree algorithm would suffice to answer the open question affirmatively.

Published
2007

22. Kinetic Maintenance of Mobile k-Centre in Trees

Author

Durocher, Stéphane, Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
High Energy Physics::Experiment, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; Let C denote a set of n mobile clients, each of which follows a continuous trajectory on a weighted tree T. We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of C. When each client in C moves with linear motion along a path on T we derive a tight bound of \Theta(n) on the complexity of the motion of the 1-centre and corresponding bounds of O(n^2 \alpha(n)) and \Omega(n^2) for a 2-centre, where \alpha(n) denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2-centre of C: the 1-centre can be found in optimal time O(n \log n) when the distance function between mobile clients is known or O(n^2) when the function must be calculated, and a 2-centre can be found in time O(n^2 \log n). These algorithms lend themselves to implementation within the framework of kinetic data structures, resulting in structures that are compact, efficient, responsive, and local.

Published
2007

23. Kinetic Maintenance of Mobile k-Centres in Trees

Author

Paul, Christophe, Durocher, Stéphane, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and LIRMM

Subjects
velocity, facility location, 2-centre, High Energy Physics::Experiment, mobile, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], continuous, kinetic data structure, centre, tree
Abstract

Given a set P of points (clients) on a weighted tree T, the k-centre of P corresponds to a set of k points (facilities) on T such that the maximum graph distance between any client and its nearest facility is minimized. We consider the mobile k-centre problem on trees. Let C denote a set of n mobile clients, each of which follows a continuous trajectory on T. We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of C. When each client in C moves with linear motion along a path on T, the motions of the corresponding 1-centre and 2-centre are piecewise linear; we derive a tight combinatorial bound of $\Theta(n)$ on the complexity of the motion of the 1-centre and corresponding bounds of $O(n^2 \alpha(n))$ and $\Omega(n^2)$ for the 2-centre, where $\alpha(n)$ denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2-centre of C: the 1-centre can be found in optimal time $O(n \log n)$ when the distance function between mobile clients is known or $O(n^2)$ when the function must be calculated, and a 2-centre can be found in time $O(n^2 \log n)$. These algorithms lend themselves to implementation within the framework of kinetic data structures, resulting in structures that are compact, efficient, responsive, and local.

Published
2006

24. Aspects algorithmiques de la décomposition modulaire

Author

Paul, Christophe, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université Montpellier II - Sciences et Techniques du Languedoc, and J.C. Konig

Subjects
Graph theory, Algorithmes, Modular decomposition, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Théorie des graphes, Décomposition modulaire, [MATH]Mathematics [math], Algorithms
Abstract

Modular decomposition arises in different topics of combinatorics, e.g. graph theory. This decomposition is a powerful description tool for discrete objects. It is also used as a preliminary step of many algorithms.This dissertation deals with the algorithmic aspects of modular decomposition. Although linear time algorithms have been published in the mid 90's, the research on that problem still continue on. We survey the advances and techniques recently developped.; La décomposition modulaire apparait naturellement dans différents domaines de la combinatoire (et en particulier les graphes). Cette décomposition se révèle être un puissant outil de description d'objets discrets. Elle est aussi utilisée comme étape préliminaire à nombreux d'algorithmes.Dans ce mémoire, nous nous intéressons au calcul de la décomposition modulaire. Malgré la publication d'algorithmes linéaires au milieu des années 90, la recherche sur ce problème n'a pas cessée. Nous faisons le point sur les différentes avancées et techniques utilisées.

Published
2006

25. Edge Maximal Graphs of Branchwidth k

Author

Paul, Christophe, Telle, Jan Arne, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
Physics::Popular Physics, Mathematics::History and Overview, Computer Science::Digital Libraries, Computer Science::Computers and Society
Abstract

Electronic Notes in Discrete Mathematics; International audience

Published
2005

26. New Tools and Results for Branchwidth

Author

Paul, Christophe, Telle, Jan Arne, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], GRAPHS
Abstract

We provide new tools for the study of branchwidth of graphs, such as $k$-troikas and good subtree-representations, that allow us to give several new results. We show that a graph $G$ has branchwidth at most $k$ if and only if it is a subgraph of a chordal graph in which every maximal clique has a $k$-troika respecting its minimal separators. Moreover, if $G$ itself is chordal with clique tree $T$ then such a chordal supergraph exists having clique tree a minor of $T$. We use these tools to give a straightforward $O(m+n+q^2)$ algorithm computing branchwidth for an interval graph on $m$ edges, $n$ vertices and $q$ maximal cliques. We also prove a conjecture of F. Mazoit \cite{Maz04a} by showing that branchwidth is polynomial on a chordal graph given with a clique tree having a polynomial number of subtrees. Finally, we propose a characterization of $k$-branches, namely those graphs of branchwidth $k$ having a maximal set of edges.

Published
2005

27. Characterization and Algorithmic Generation of k-Branches

Author

Paul, Christophe, Telle, Jan Arne, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
WIDTH PARAMETER, GRAPH DECOMPOSITION
Published
2005

28. Eclectisme dans les petits mondes

Author

Fraigniaud, Pierre, Gavoille, Cyril, Paul, Christophe, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

National audience

Published
2004

29. Approximate Multicommodity Flow for WDM Networks Design

Author

Bouklit, Mohamed, Coudert, David, Lalande, Jean-François, Paul, Christophe, Rivano, Hervé, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Gouat, Isabelle

Subjects
Multicommodity flow, dynamic shortest paths, WDM networks design, RWA, [INFO]Computer Science [cs], [INFO] Computer Science [cs]
Abstract

International audience; The design of WDM optical networks is an issue for telecom operators since the spreading of this technology will not occur unless enough performance guarantees are provided. Motivated by the quest for efficient algorithms for the Routing and Wavelength Assignment problem (RWA), we address approximations of the fractional multicommodity flow problem which is the central part of a complex randomized rounding algorithm for the integral problem. Through the use of dynamic shortest path computations and other combinatorial approaches, we improve on the best known algorithm. We also provide directions for further improvements.

Published
2003

30. Distance Labeling and Split Decomposition

Author

Gavoille, Cyril, Paul, Christophe, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
Distance-hereditary graphs, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Split decomposition, Distance labeling scheme, ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2003

31. Small Universal Distance Matrices

Author

Gavoille, Cyril, Paul, Christophe, Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Algorithmes, Graphes et Combinatoire (ALGCO), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
STRUCTURE DE DONNEES DISTRIBUEES, REPRESENTATION IMPLICITE, ETIQUETAGE DE DISTANCE
Published
2003

32. Optimal Distance Labeling Schemes for Interval and Circular-arc Graphs

Author

Gavoille, Cyril, Paul, Christophe, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Gavoille, Cyril

Subjects
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]
Published
2003

33. Eclecticism Shrinks the World

Author

Fraigniaud, Pierre, Gavoille, Cyril, Paul, Christophe, Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Algorithmes, Graphes et Combinatoire (ALGCO), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Abstract

numéro du rapport : TR-LRI-1376

Published
2003

34. Quelques algorithmes linéaires de reconnaissance autour de Lex-BFS

Author

Paul, Christophe, Viennot, Laurent, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Informatique Théorique et Programmation (LITP), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Université Pierre et Marie Curie - Paris 6 (UPMC)

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-WB]Computer Science [cs]/Web, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

Ecole AMI, Nice, décembre 1996; Nous présesentons dans cet article des algorithmes de reconnaissances pour différentes classes de graphes (co-triangulés, intervalles, convexes, ...) tous basés sur Lex-BFS. Ces algorithmes sont optimaux, linéaires en la taille du graphe, et simples : ils évitent l'utilisation des PQ-arbres et de la décomposition modulaire.

Published
1997

Catalog

Books, media, physical & digital resources
See catalog results