Projet ANR graal - Publications

Accueil | Réunions | Participants | Publications | Contacts

Journaux
Conférences
Exposés invités
Thèses et Habilitations
Livres et chapitres de livres


Journal papers

[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



Conference papers

[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.


Books and chapters

[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.