Publications
Cette page recense toutes les publications produites dans le cadre du projet GraphEn.
Website
| TRAG-WEB : Term Rewriting Automata and Graphs | ||
| I. Durand and M. Raskin. |
Journal articles
| On the multipacking number of grid graphs. | ||
| L. Beaudou and R.C. Brewster. | ||
| Discrete Mathematics & Theoretical Computer Science,21(3)(2019). |
| Bisplit graphs satisfy the Chen-Chvátal conjecture. | ||
| L. Beaudou, G. Kahn and M. Rosenfeld. | ||
| Discrete Mathematics & Theoretical Computer Science,21(1)(2019). |
| Grammars and clique-width bounds from split decompositions. | ||
| B. Courcelle. | ||
| Discrete Applied Mathematics 2019. |
| On quasi-planar graphs: Clique-width and logical description. | ||
| B. Courcelle. | ||
| Discrete Applied Mathematics, 2019. |
| Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs. | ||
| P.A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi. | ||
| Discrete Applied Mathematics 265: 69-85 (2019). |
| Enumeration and Maximum Number of Minimal Dominating Sets for Chordal Graphs. | ||
| P.A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi. | ||
| Theor. Comput. Sci. 783: 41-52 (2019). |
| Fast exact algorithms for some connectivity problems parameterized by clique-width. | ||
| B. Bergougnoux and M.M. Kanté. | ||
| Theoretical Computer Science 782: 30-53 (2019). |
| Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques. | ||
| M. Liedloff, P. Montealegre and I. Todinca. | ||
| Algorithmica 81(3): 986-1005 (2019). |
| Counting minimal transversals of β-acyclic hypergraphs. | ||
| B. Bergougnoux and M.M. Kanté. | ||
| J. Comput. Syst. Sci. 101: 21-30 (2019). |
| Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph. | ||
| A. Conte, M.M. Kanté, Y. Otachi, T. Uno and K. Wasa. | ||
| Theoretical Computer Science, 2018. |
| Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques. | ||
| F. Fomin, M. Liedloff, P. Montealegre and I. Todinca. | ||
| Algorithmica 80(4): 1146-1169 (2018). |
| Enumeration of maximal irredundant sets for claw-free graphs. | ||
| Petr A. Golovach, Dieter Kratsch, Mohamed Yosri Sayadi. | ||
| Theor. Comput. Sci. 754: 3-15 (2019). |
| Representation of lattices via set-colored posets. | ||
| M. habib, L. Nourine. | ||
| Discrete Applied Mathematics 249: 64-73 (2018). |
| Algorithms for computing the Shapley value of Cooperative Games on Lattices. | ||
| K. Maafa, L. Nourine, M. Said Radjef. | ||
| Discrete Applied Mathematics 249: 91-105 (2018). |
| Enumerating minimal connected dominating sets in graphs of bounded chordality. | ||
| P.A. Golovach, P. Heggernes, D. Kratsch. | ||
| Theor. Comput. Sci. 630: 63-75 (2016) |
| Output-polynomial enumeration on graphs of bounded (local) linear mim-width. | ||
| P.A. Golovach, P. Heggernes, M.M. Kanté, D. Kratsch, S.H. Sæther, and Y. Villanger. | ||
| Algorithmica 80(2): 714-741 (2018). |
| Minimal dominating sets in interval graphs and trees. | ||
| P.A. Golovach, P. Heggernes, M.M. Kanté, D. Kratsch, and Y. Villanger. | ||
| Discrete Applied Mathematics, 216:162-170, 2017. |
| Enumeration and maximum number of minimal connected vertex covers in graphs. | ||
| P.A. Golovach, P. Heggernes, D. Kratsch. | ||
| Eur. J. Comb. 68: 132-147 (2018) |
| Computations by fly-automata beyond monadic second-order logic. | ||
| B. Courcelle and I. Durand. | ||
| Theoretical Computer Science, 619 (2016) 32-67. |
| From tree-decompositions to clique-width terms. | ||
| B. Courcelle. | ||
| Discrete Applied Mathematics 248: 125-144 (2018). |
| Fly-automata for checking MSO2 graph properties. | ||
| B. Courcelle. | ||
| Discrete Applied Mathematics 245: 236-252 (2018). |
| Algorithms for k-meet-semidistributive lattice. | ||
| L. Beaudou, A. Mary and L. Nourine. | ||
| Theoretical computer science, 658: 391-398 (2017) |
| Extended dualization: Application to maximal pattern mining. | ||
| L. Nourine and J.-M. Petit. | ||
| Theoretical Computer Science, Volume 618, 7 March 2016, Pages 107-121. |
Book Chapters (preliminary to the beginning of the project)
| Model-checking with Fly-automata. | ||
| B. Courcelle and I. Durand. | ||
| In Encyclopedia of Algorithms, second edition, Springer, 2016 |
| Minimal dominating set enumeration. | ||
| M.M. Kanté and L. Nourine. | ||
| In Encyclopedia of Algorithms, second edition, Springer, 2016. |
International Conferences or Workshops with Proceedings
| Neighborhood preferences for minimal dominating sets enumeration. | ||
| O. Defrain and L. Nourine. | ||
| ISAAC 2019, arxiv:1805.02412. |
| A Stay-in-a-Set Game without a Stationary Equilibrium. | ||
| Kristoffer Arnsfelt Hansen and Mikhail Raskin. | ||
| GandALF 2019. |
| More applications of the d-neighbor equivalence: acyclic and connectivity constraints. | ||
| B. Bergougnoux and M.M. Kanté. | ||
| ESA 2019, arxiv:1805.11275v4. |
| Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs. | ||
| A. Conte, R. Grossi, M.M. Kanté, A. Marino, T. Uno, K. Wasa. | ||
| MFCS 2019. |
| Maximal Irredundant Set Enumeration in Bounded-Degeneracy and Bounded-Degree Hypergraphs. | ||
| A. Conte, M.M. Kanté, A. Marino, T. Uno. | ||
| IWOCA 2019. |
| Dualization in lattices given by implicational bases. | ||
| O. Defrain and L. Nourine. | ||
| ICFCA 2019, arxiv:1901.07503, 2019. |
| Enumerating minimal dominating sets in triangle-free graphs. | ||
| M. Bonamy, O. Defrain, M. Heinrich, J.-F. Raymond | ||
| STACS 2019. |
| A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton. | ||
| M. Raskin | ||
| ICALP 2018. |
| On Minimum Connecting Transition Sets in Graphs. | ||
| B. Bergougnoux and T. Bellitto | ||
| WG 2018. |
| Computing Small Pivot-Minor. | ||
| K.K. Dabrowski, F. Dross, J. Jeong, M. M. Kanté, O-J. Kwon, S. Oum, D. Paulusma | ||
| WG 2018. |
| Enumerating Minimal Transversals of Hypergraphs without Small Holes. | ||
| M.M. Kanté, K. Khoshkhah, M. Pourmoradnasseri | ||
| MFCS 2018. |
| On Maximal Cliques with Connectivity Constraints in Directed Graphs. | ||
| A. Conte, M.M. Kanté, T. Uno, K. Wasa. | ||
| ISAAC 2017. |
| Efficient Enumeration of Maximal $k$-Degenerate Subgraphs in a Chordal Graph. | ||
| A. Conte, M.M. Kanté, Y. Otachi, T. Uno, K. Wasa. | ||
| COCOON 2017. |
| An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width. | ||
| B. Bergougnoux, M.M. Kanté, O-J. Kwon. | ||
| WADS 2017. |
| Fly-automata for checking monadic second-order properties of graphs of bounded tree-width. | ||
| B. Courcelle. | ||
| Conference LAGOS, Brazil, Electronic notes in Computer Science, 50 (2015) 3-8. |
| Removing redundant tests by replicating control paths. | ||
| I. Durand and R. Strandh, | ||
| 10th European Lisp Symposium, Belgium, 106--112 (2017). |
| Writing a best-effort portable code walker in Common Lisp. | ||
| M. Raskin, | ||
| 10th European Lisp Symposium, Belgium, 98--105 (2017). |
| A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model. | ||
| M. Raskin. | ||
| ICALP, 88:1--88:12 (80), 2017. |
| Enumeration of Maximal Irredundant Sets for Claw-Free Graphs. | ||
| P.A. Golovach, Dieter Kratsch, Mohamed Yosri Sayadi. | ||
| CIAC, 297-309, 2017 |
| Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs. | ||
| P.A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi. | ||
| WG, 289-302, 2017 |
| Counting Minimal Dominating Sets. | ||
| M.M. Kanté and T. Uno. | ||
| TAMC 2017 / Lecture Notes in Computer Science (LNCS), Springer, 2017. |
| Enumerating Minimal Tropical Connected Sets. | ||
| D. Kratsch, M. Liedloff, M.Y. Sayadi. | ||
| SOFSEM 2017: 217-228 |
| Efficient Enumeration of Solutions Produced by Closure Operations. | ||
| A. Mary and Y. Strozecki. | ||
| 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47, pages 52:1-52:13, Dagstuhl, Germany, 2016. |
| Token Jumping in Minor-Closed Classes. | ||
| N. Bousquet, A. Mary, A. Parreau. | ||
| FCT, 2017. |
National Conferences or Workshops without proceedings
| Enumeration of Minimal Connected Dominating Sets in chordal bipartite graphs. | ||
| B. Gras and M. Liedloff. | ||
| Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW) 2019. |
| Structured graphs and the verification of their monadic second-order properties by means of automata. | ||
| B. Courcelle (exposé invité). | ||
| Russian Workshop on Complexity and Model Theory, 2019. |
| Demonstration of a software: Monadic second-order model checking with fly-automata. | ||
| B. Courcelle (exposé invité). | ||
| Russian Workshop on Complexity and Model Theory, 2019. |
| Verification of logically defined graph properties - Monadic second-order properties of graphs of bounded tree-width or clique-width. Demonstration of the software TRAG. | ||
| B. Courcelle (exposé invité). | ||
| GT CoA'19 (Roscoff) |
| Optimization Problems via Minimal Triangulations and Potential Maximal Cliques. | ||
| I. Todinca and P. Montealegre. | ||
| 2016 SIAM Conference on Discrete Mathematics, Atlanta, USA |
| Hybrid algorithms for candidate keys enumeration for a relational schema. | ||
| K. Ennaoui and L. Nourine. | ||
| BDA'2016, Futuroscope, Poitiers - France, 15 au 18 Novembre, 2016 |
| On Maximal Irredundant Sets and (sigma, rho)-Dominating Sets in Paths. | ||
| P.A. Golovach, D. Kratsch, M. Liedloff, M. Rao and M.Y. Sayadi. | ||
| Workshop on Enumeration Problems and Applications, 2016 |
Manuscripts
| On the maximum number of minimal connected dominating sets in convex bipartite graphs. | ||
| Mohamed Yosri Sayadi. | ||
| arxiv:1908.02174, 2019. |
| Translating between the representations of a ranked convex geometry. | ||
| O. Defrain, L. Nourine and S. Vilmin. | ||
| arxiv:1907.09433, 2019. |
| Bounding the number of (σ, ρ)-dominating sets in trees, forests and graphs of bounded pathwidth. | ||
| M. Rosenfeld. | ||
| Submitted, 2019. |
| On the dualization in distributive lattices and related problems. | ||
| O. Defrain, L. Nourine and T. Uno. | ||
| arxiv:1901.07004, 2019. |
| Maximal Strongly Connected Cliques in Directed Graphs: Algorithms and Bounds. | ||
| A. Conte, M.M. Kanté, T. Uno and K. Wasa. | ||
| Submitted, 2019. |
