Projet ANR graal - PublicationsAccueil | Réunions | Participants | Publications | ContactsJournaux [J1] A. Bergeron, S. Bérard, C. Chauve, and C. Paul. Sorting by Intervals with Common Intervals is not Always Difficult. IEEE-ACM Transaction on Computational Biology and Bioinformatics, 4(1):4-16, 2007.
[J2] M.M. Kanté. Vertex-minor reduction can simulate edge contractions. Discrete Applied Mathematics, 155(17):2328-2340, 2007. [J3] M. Habib and D. Kelly and E. Lebhar and C. Paul. Can transitive orientation make sandwich problems easier ? Discrete Mathematics, 307(16):2030-2041, 2007. [J4] E. Gioan and M. Las Vergnas. On the evaluation at (j,j^2) of the Tutte polynomila of a ternary matroid. Journal of Algebraic Combinatorics 25:1-6, 2007. [J5] E. Gioan. Enumerating degree sequences in digraphs and a cycle-cocycle reserving system. Europpean Journal of Combinatorics, 28(4):1351-1366, 2007. [J6] M.P. Debson and M. Gutierrez and M. Habib and J. Szwarcfiter. On transitive orientations with restricted covering graphs. Information Processing Letters, 101(3):119-125, 2007. [J7] M. Rao. MSOL partitioning problems on graphs of bounded treewidth and cliquewidth. Theoretical Computer Science, 377(1-3):260-267, 2007. [J8] B. Courcelle and S.I. Oum. Vertex-minor, monadic second order and a conjecture by Seese. Journal of Combinatorial Theory Series B, 97(1):91-126, 2007. [J9] Y. Dourisboure and C. Gavoille. Tree-decomposition with bags of small diameter. Discrete Mathematics 307(16):2008-2029, 2007. [J10] Y. Dourisboure, F.F. Dragan, C. Gavoille, C. Yan. Spanners for bounded tree-length graphs. Theoretical Computer Science 383(1): 34-44, 2007. [J11] B. Courcelle and C. Delhommé. The modular decomposition of countable graphs : Definition and construction in monadic second-order logic. Theoretical Computer Science, 394:1-38, 2008. [J12] S. Bérard and C. Chauve and C. Paul. A more efficient algorithm for perfect sorting by reversals. Information Processing Letters, 106:90-95, 2008. [J13] F. Mazoit and N. Nisse. Monotonicity of non-deterministic graph searching. Theoretical Computer Science, 399(3):169-178, 2008. [J14] B.M. Bui-Xuan and M. Habib and C. Paul. Competitive graph searches. Theoretical Computer Science, 393(1-3):72-80, 2008. [J15] B. Courcelle. Circle graphs and Monadic Second-order logic. To appear in Journal of Applied Logic, 6:416-422, 2008. [J16] B. Courcelle. A multivariate interlace polynomial. Electronic Journal of Combinatorics, 15(1), 2008. [J18] A. Bretscher, D. Corneil, M. Habib and C. Paul. A simple linear time LexBFS cograph recognition algorithm. SIAM Journal on Discrete Mathematics, 22(4):1277-1296, 2008. [J19] C. Gavoille and C. Paul, Optimal Distance Labeling for Interval and Circular-Arc Graphs. SIAM Journal on Discrete Mathematics, 22(3):1239-1258, 2008. [J20] P. Charbit, M. Habib, V. Limouzy, F. de Montgolfier, M. Raffinot, M. Rao. A note on computing set overlap classes. Information Processing Letters, 108(4):186-191, 2008. [J21] A. Bergeron, C. Chauve, F. de Montgolfier, M. Raffinot: Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs. SIAM Journal on Discrete Mathematics 22(3):1022-1039, 2008. [J22] M. Rao. Solving some NP-complete problems using split decomposition. Discrete Applied Mathematics, 156(14):2768-2780, 2008. [J23] M. Rao. Clique-width of graphs defined by one-vertex extensions. Discrete Mathematics, 308(24):6157-6165, 2008. [J24] E. Gioan. Cicrcuit-cocircuit reserving systems in regular matroids. Annals of Combinatorics, 12(2):171-182, 2008. [J25] F. Mazoit and N. Nisse. Monotonicity of non-deterministic graph searching, Theoretical Computer Science, 399(3):169-178, 2008. [J26] B. Courcelle and M. Kanté. Graph operations characterizing rank-width. Discrete Applied Mathematics, 157(4):627-640, 2009. [J27] O. Amini, F. Mazoit, N. Nisse and S. Thomassé. Submodular Partition Functions. In Discrete Mathematics, ???:???-???, 2009. [J28] F. Fomin, F. Mazoit and I. Todinca. Computing branchwidth via efficient triangulations and blocks. Discrete Applied Mathematics, 157(12):2726-2736, 2009. [J29] C. Paul and J.A. Telle. Edge maximal graphs of branchwidth k : the k-branches. In Discrete Mathematics, 309(6):1467-1475, 2009. [J30] Y. Villanger, P. Heggerness, C. Paul and J.A. Telle. Interval completion with few edges. In SIAM Journal on Computing, 38(5):2007-2020 , 2009. [J31] C. Paul and J.A. Telle. Branchwidth of chordal graphs. In Discrete Applied Mathematics 157(12):2718-2725, 2009. [J32] V. Berry, S. Guillemot, F. Nicolas and C. Paul. Linear time 3-approximation for MAST problem. In ACM Transcations on Algorithms, 5(2):1-18, 2009. [J33] C. Crespelle and C. Paul. Fully Dynamic Algorithm for Modular decomposition and recognition of permutation graphs. In Algorithmica, ???:???-???, 2009. [J34] F. Fomin, S. Gaspers, S., Saurabh, A. Stepanov. On Two Techniques of Combining Branching and Treewidth. Algorithmica 54(2):181-207, 2009.
[J35] F. Carrère. Inductive computations on graphs defined by clique-width expressions. RAIRO Theor. Inf. Appl. 43:625-65, 2009
[C1]
B.-M. Bui Xuan, M. Habib, V. Limouzy and F. de
Montgolfier: Homogeneity vs. Adjacency: Generalising Some Graph
Decomposition Algorithms. In 32nd International Workshop on Graph Theoretical Concepts in Computer Science - WG, number 4271
in Lecture Notes in Computer Science,
pages 278-288, 2006.
[C2] C. Paul, A. Proskurowski and J.A. Telle. Generation of graphs with bounded branchwidth. In 32nd International Workshop on Graph Theoretical Concepts in Computer Science - WG, number 4271 in Lecture Notes in Computer Science, pages 206-216, 2006. [C3] B. Courcelle and A. Twigg. Compact forbidden-set routing. In Symposium on Theoretical Aspect of Computer Science - STACS, number 4393 in Lecture Notes in Computer Science, pages 37-48, 2007. [C4] P. Heggerness, C. Paul, J.A. Telle and Y. Villanger. Interval completion with few edges. In ACM Symposium on Theory of Computing - STOC, pages 347-381, 2007. [C5] F. Mazoit and N. Nisse. Monotonicity of Non-deterministic Graph Searching. In International Workshop on Graph Theoretical Concepts in Computer Science - WG, number 4769 in Lecture Notes in Computer Science, pages 33-44, 2007. [C6] P. Gambette and S. Vialette. On restrictions of balanced 2-interval graphs. In International Workshop on Graph Theoretical Concepts in Computer Science - WG. in Lecture Notes in Computer Science 4769:55-65, 2007. [C7] V. Limouzy, F. de Montgolfier and M. Rao. NLC-2 graph recognition and isomorphism. In International Workshop on Graph Theoretical Concepts in Computer Science - WG inumber 4769 in Lecture Notes in Computer Science, pages 86-98, 2007. [C8] B. Courcelle and M.M. Kanté. Graph operations characterizing rank-width and balanced graph expressions. In International Workshop on Graph Theoretical Concepts in Computer Science - WG number 4769 in Lecture Notes in Computer Science, pages 66-75, 2007. [C9] C. Gavoille and A. Labourel. Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs. In Annual European Symposium on Algorithms - ESA, number 4698 in Lecture Notes in Computer Science, pages 582-593, 2007. [C10] B. Courcelle and C. Gavoille and M. Kanté and D.A. Twigg. Forbidden-set Lableing on Graphs. In 2nd Workshop on Locality Preserving Disctributed Computing Methods (LOCALITY), 2007. [C12] I. Abraham and C. Gavoille and D. Malkhi and U. Wieder. Strong-Diameter Decompositions of Minor Free Graphs. Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA, pages 16-24, 2007. [C13] B.M. Bui-Xuan and M. Habib and V. Limouzy and F. de Montgolfier. Unifying Two Graph Decompositions with Modular Decomposition. In International Symposium on Algorithms and Computation - ISAAC, number 4835 in Lecture Notes in Computer Science, pages 52-64, 2007 [C14] E. Gioan and C. Paul. Dynamic Distance Hereditary Graphs Using Split Decomposition. In International Symposium on Algorithms and Computation - ISAAC, number 4835 in Lecture Notes in Computer Science, pages 41-51, 2007. [C15] F. Mazoit and S. Thomassé. Branchwidth of graphic matroids. In Surveys in Combinatorics, London Mathematical Society Lecture Note Series, pages 275-286, 2007. [C16] B. Courcelle, C. Gavoille, M.M. Kanté. Efficient First-Order Model-Checking Using Short Labels. Annual International Workshop Frontiers in Algorithmics - FAW, number 4957 in Lecture Notes in Computer Science, pages 159-170, 2008. [C17] B.M. Bui-Xuan, M. Habib. A Representation Theorem for Union-Difference Families and Application. In Latin American Symposium on Theoretical Informatics - LATIN, number 4957 in Lecture Notes in Computer Science, pages 492-503, 2008. [C18] B. Courcelle, C. Gavoille, M.M. Kanté and A.D. Twigg. Connectivity Check in Plane 3-Connected Graphs with Short Labels Based on Integer Coordinates. International Conference on Topological and Geometric Graph Theory - TGGT, Electronic Notes in Discrete Mathematics, 31:151-155, 2008. [C19] M. Tedder, D. Corneil, M. Habib and C. Paul. Simple, linear-time modular decomposition. In International Colloquium on Automata, Languages and Programming - ICALP. Number 5125 in Lecture Notes in Computer Science, pages 634-645, 2008. [C20] S. Bérard, A. Chateau, C. Chauve, C. Paul and E. Tannier. Perfect DCJ rearrangement. In Annual RECOMB Satellite Workshop on Comparative Genomic - RCG. Number 5267 in Lecture Notes in Bioinformatics, pages 156-167, 2008. [C21] L. Addario-Berry, O. Amini, J.S. Sereni, S. Thomasse. Guarding Art Galleries: The Extra Cost for Sculptures is Linear. In Scandinavian Workshop on Algorithm Theory. Number 5124 in Lectures Notes in Computer Science, pages 41-52, 2008. [C22] V. Chepoi, F. Dragan, B. Estellon, M. Habib, Y. Vaxès. Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graph. In ACM Symposium on Computational Geometry, pages 59-68, 2008. [C23] M. Chapelle, F. Mazoit and I Todinca. Constructing brambles. International Symposium on Mathematical Foundations of Computer Science - MFCS. Number ??? in Lecture Notes in Computer Science, pages ???, 2009. [C24] F. Mazoit. Tree-width of hypergraphs and surface duality. DIMAP workshop on Algorithmic Graph Theory - AGT. Number 32 in Electronic Notes in Discrete Mathematics, pages 93-97, 2009. [C25] M.M. Kanté et M. Rao. Directed Rank-Width and Displit Decomposition. In International Workshop on Graph Theoretical Concepts in Computer Science - WG, number ??? in Lecture Notes in Computer Science, pages ???-???, 2009. [C26] P. Gambette, V. Berry and C. Paul. The structure of level-k phylogenetic networks. In Annual Symposium on Combinatorial Pattern Matching - CPM. Number 5577 in Lecture Notes in Computer Science, pages 289-300, 2009. [C27] T.-H. To and M. Habib: Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time. In Annual Symposium on Combinatorial Pattern Matching - CPM. Number 5577 in Lecture Notes in Computer Science, pages 275-288, 2009. [C28] S. Bessy and C. Paul and A. Perez. Polynomial kernels for 3-leaf power graph modification problems. In International Workshop On Combinatorial Algorithms - IWOCA. Number ??? in Lecture Notes in Computer Science, pages ???-???, 2009. [C29] D. Huson, R. Rupp, V. Berry, P. Gambette, C. Paul. Computing Galled Networks from Real Data. Annual Conference on Intelligent Systems for Molecular Biology & European Conference on Computational Biology - ISMB/ECCB, 2009. [C30] H. Fernau, S. Gaspers, D. Kratsch, M. Liedloff, D. Raible. Exact Exponential-Time Algorithms for Finding Bicliques in a Graph. Cologne Twente Workshop on Graphs and Combinatorial Optimization - CTW, pages 205-209, 2009. [C31] S. Thomasse. A Quadratic Kernel for Feedback Vertex Set. Annual ACM-SIAM Symposium on Discrete Algorithms - SODA, pages 115-119, 2009. [C32] N. Bousquet, J. Daligault, S. Thomasse, A. Yeo. A Polynomial Kernel for Multicut in Trees. International Symposium on Theoretical Aspects of Computer Science - STACS. In number 3 of Leibniz International Proceedings in Informatics, pages 183-194, 2009. [C33] M. Habib and J. Stacho. Linear algorithms for chordal graphs of bounded directed vertex leafage. DIMAP Workshop on Algorithmic graph theory - AGT. Number 32 in Electronic Notes in Discrete Mathematics, pages 99-108, 2009. [C34] M. Habib and V. Limouzy. On some simplicial elimination schemes for chordal graphs. DIMAP Workshop on Algorithmic graph theory - AGT. Number 32 in Electronic Notes in Discrete Mathematics, pages 125-132, 2009. [C35] J. Stacho and M. Habib. Polynomial-time algorithm for the leafage of chordal graphs. In European Symposium on Algorithms - ESA. Number ??? in Lecture Notes in Computer Science, pages ???-???, 2009. [C36] M. Habib and J. Stacho. Decomposition theorem for chordal graphs and its applications. European Conference on Combinatorics, Graph Theory and Applications- EUROCOMB. Number ??? in Electronic Notes in Discrete Mathematics, pages ???-???, 2009. [C37] B.-M. Bui Xuan and M. Habib. Unifying the representation of symmetric crossing families and weakly partitive families. European Conference on Combinatorics, Graph Theory and Applications- EUROCOMB. Number ??? in Electronic Notes in Discrete Mathematics, pages ???-???, 2009. [C38] M. Habib and V. Limouzy. On some simplicial elimination schemes for chordal graphs. DIMAP Workshop on Algorithmic graph theory - AGT. Number 32 in Electronic Notes in Discrete Mathematics, pages 125-132, 2009. [C39] J. Daligault and S. Thomasse. On finding directed trees with many leaves. In International Workshop on Parameterized and Exact Computation - IWPEC. Number ??? in Lecture Notes in Computer Science, pages ???-???, 2009. Invited talks [T1] C. Gavoille. Localized data-structures. 2nd Workshop on Locality Preserving Disctributed Computing Methods (LOCALITY), 2007. [T2] S. Thomassé. Branchwidh of graphc matroids. British Combinatorial Conference, 2007. [T3] S. Thomassé. Cyclic Orderings of Matroids. 4th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2007. [T4] B. Courcelle. Gaph structure and monadic second-order logic: Language theoretical aspects. International Colloquium on Automata, Languages and Programming - ICALP, number 5125(1) in Lectures Notes in Computer Science, pages 1-13, 2008. [T5] B. Courcelle. Monadic second-order logic for graphs : algorithmic and language theoretical applications. Language Automata Theory and Applications - LATA, number 5457 in Lectures Notes in Computer Science, pages 19-22, 2009. [T6] M. Habib. Diameter and Center Computations in Networks. Cologne-Twente Workshop on Graphs and Combinatorial Optimization - CTW, pages 257-258, 2009.
Dissertations (PhDs and habilitations)
[D1] C. Paul. Aspects algorithmiques de la décomposition modulaire. Habilitation à diriger des recherches, Université de Montpellier 2, France, 2006. [D2] C. Crespelle. Représentation dynamiques de graphes. Thèse de doctorat. Université de Montpellier 2, France, 2007[D3] A. Labourel. Partition d'arêtes et représentation implicite de graphes. Thèse de doctorat. Université de Bordeaux 1, France, 2007. [D4] B.-M. Bui-Xuan. Tree-Representation of Set Families in Graph Decompositions and Efficient Algorithms. Thèse de doctorat, Université Montpellier II, France, 2008 [D5] M. Kanté. Graph Structurings: Some Algorithmic Applications. Thèse de doctorat. Université de Bordeaux 1, France, 2008.
[D6] V. Limouzy. ???. Thèse de doctorat. Université de Paris 7, France, 2008.
[B1] B. Courcelle. Décomposition arborescentes. Chapter 6 in Graphes et applications 2, J.C. Fournier ed., Hermès-Lavoisier, p.195-231, 2007.
[B2] B. Courcelle. Quantifier-free definable graph operations preserving recognizability. Chapter in Logic and Automata, History and Perspectives, J. Flum and E. Grädel and T. Wilke ed. Number 2 in Texts in Logic and Games, Amsterdam University Press, pages 251-260, 2008. [B3] M. Habib and C. Paul. Proceedings of International Workshop on Graph Theoretical Concepts in Computer Science. Lecture Notes in Computer Science number ???, 2009. |