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

Model-checking with Fly-automata,.
B. Courcelle and I. Durand.
In Encyclopedia of Algorithms, second edition., Springer., Ming-Yang Kao  ed., Chapitre 20, 2015

 

Minimal dominating set enumeration.
M.M. Kanté and L. Nourine.
In Encyclopedia of Algorithms : 1287-1291. 2016.

 

International Conferences or Workshops with Proceedings

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

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.

 

Neighborhood preferences for minimal dominating sets enumeration.
O. Defrain and L. Nourine.
arxiv:1805.02412, 2018.

 

Published on  September 6th, 2019