E. H. Bachoore and H. L. Bodlaender, Finally, the branch-and-bound algorithm presented in this paper (without the pre-processing phase) is now included in Sagemath and so it can be used by others to perform comparisons on a fair basis New upper bound heuristics for treewidth, 4th InternationalWorkshop on Experimental and Efficient Algorithms (WEA), pp.216-227, 2005.

E. H. Bachoore and H. L. Bodlaender, A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth, Second International Conference on Algorithmic Aspects in Information and Management, AAIM, pp.255-266, 2006.
DOI : 10.1007/11775096_24

J. Barát, Directed Path-width and Monotonicity in Digraph Searching, Graphs and Combinatorics, vol.22, issue.2, pp.161-172, 2006.
DOI : 10.1007/s00373-005-0627-y

D. Berwanger, A. Dawar, P. Hunter, S. Kreutzer, and J. Obdrzálek, The dag-width of directed graphs, Journal of Combinatorial Theory, Series B, vol.102, issue.4, pp.900-923, 2012.
DOI : 10.1016/j.jctb.2012.04.004

T. C. Biedl, T. Bläsius, B. Niedermann, M. Nöllenburg, R. Prutkin et al., Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings, Graph Drawing, pp.460-471, 2013.
DOI : 10.1007/978-3-319-03841-4_40

D. Bienstock, Graph searching, path-width, tree-width and related problems (a survey), DIMACS Ser. in Discrete Mathematics and Theoretical Computer Science, vol.5, pp.33-49, 1991.

D. Bienstock and P. D. Seymour, Monotonicity in graph searching, Journal of Algorithms, vol.12, issue.2, pp.239-245, 1991.
DOI : 10.1016/0196-6774(91)90003-H

H. L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, vol.25, issue.6, pp.1305-1317, 1996.
DOI : 10.1137/S0097539793251219

H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, vol.209, issue.1-2, pp.1-45, 1998.
DOI : 10.1016/S0304-3975(97)00228-4

H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, pp.75423-434, 2009.
DOI : 10.1016/j.jcss.2009.04.001

H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov et al., An o(c k n) 5-approximation algorithm for treewidth, 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.499-508, 2013.

H. L. Bodlaender, F. V. Fomin, A. M. Koster, D. Kratsch, and D. M. Thilikos, A Note on Exact Algorithms for Vertex Ordering Problems on Graphs, Theory of Computing Systems, vol.42, issue.3, pp.420-432, 2012.
DOI : 10.1007/s00224-011-9312-0

H. L. Bodlaender, F. V. Fomin, A. M. Koster, D. Kratsch, and D. M. Thilikos, On exact algorithms for treewidth, ACM Transactions on Algorithms, vol.9, issue.1, p.12, 2012.
URL : https://hal.archives-ouvertes.fr/lirmm-00804792

H. L. Bodlaender, J. Gustedt, and J. A. Telle, Linear-time register allocation for a fixed number of registers, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.574-583, 1998.
URL : https://hal.archives-ouvertes.fr/inria-00549654

H. L. Bodlaender, B. M. Jansen, and S. Kratsch, Kernel Bounds for Structural Parameterizations of Pathwidth, 13th Scandinavian Symp. and Workshops on Algorithm Theory (SWAT), pp.352-363, 2012.
DOI : 10.1007/978-3-642-31155-0_31

H. L. Bodlaender and T. Kloks, Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs, Journal of Algorithms, vol.21, issue.2, pp.358-402, 1996.
DOI : 10.1006/jagm.1996.0049

H. L. Bodlaender, T. Kloks, and D. Kratsch, Treewidth and Pathwidth of Permutation Graphs, SIAM Journal on Discrete Mathematics, vol.8, issue.4, pp.606-616, 1995.
DOI : 10.1137/S089548019223992X

H. L. Bodlaender and A. M. Koster, On the maximum cardinality search lower bound for treewidth, Discrete Applied Mathematics, vol.155, issue.11, pp.1348-1372, 2007.
DOI : 10.1016/j.dam.2007.02.004

H. L. Bodlaender and A. M. Koster, Treewidth computations I. Upper bounds, Information and Computation, vol.208, issue.3, pp.259-275, 2010.
DOI : 10.1016/j.ic.2009.03.008

URL : http://doi.org/10.1016/j.ic.2009.03.008

H. L. Bodlaender and A. M. Koster, Treewidth computations II. Lower bounds, Information and Computation, vol.209, issue.7, pp.1103-1119, 2011.
DOI : 10.1016/j.ic.2011.04.003

H. L. Bodlaender and R. H. Möhring, The Pathwidth and Treewidth of Cographs, SIAM Journal on Discrete Mathematics, vol.6, issue.2, pp.181-188, 1993.
DOI : 10.1137/0406014

N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, and N. Nisse, Tradeoffs in process strategy games with application in the WDM reconfiguration problem, Theoretical Computer Science, vol.412, issue.35, pp.4675-4687, 2011.
DOI : 10.1016/j.tcs.2011.05.002

URL : https://hal.archives-ouvertes.fr/inria-00495443

D. Coudert, F. Huc, D. Mazauric, N. Nisse, and J. Sereni, Reconfiguration of the routing in WDM networks with two classes of services, Optical Network Design and Modeling (ONDM), pp.1-6, 2009.
URL : https://hal.archives-ouvertes.fr/inria-00423453

D. Coudert, D. Mazauric, and N. Nisse, Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth, 13th International Symposium on Experimental Algorithms (SEA), pp.46-58, 2014.
DOI : 10.1007/978-3-319-07959-2_5

URL : https://hal.archives-ouvertes.fr/hal-01266496

D. Coudert and J. Sereni, Characterization of graphs and digraphs with small process numbers, Discrete Applied Mathematics, vol.159, issue.11, pp.1094-1109, 2011.
DOI : 10.1016/j.dam.2011.03.010

B. Courcelle and M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs, Theoretical Computer Science, vol.109, issue.1-2, pp.49-82, 1993.
DOI : 10.1016/0304-3975(93)90064-Z

N. Deo, S. Krishnamoorthy, and M. A. Langston, Exact and Approximate Solutions for the Gate Matrix Layout Problem, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.6, issue.1, pp.79-84, 1987.
DOI : 10.1109/TCAD.1987.1270248

J. Díaz, J. Petit, and M. Serna, A survey of graph layout problems, ACM Computing Surveys, vol.34, issue.3, pp.313-356, 2002.
DOI : 10.1145/568522.568523

A. Drucker, New limits to classical and quantum instance compression, 53rd Annual IEEE Symposium on Foundations of Computer ScienceFOCS), pp.609-618, 2012.

A. Duarte, L. F. Escudero, R. Martí, N. Mladenovic, J. J. Pantrigo et al., Variable neighborhood search for the Vertex Separation Problem, Computers & Operations Research, vol.39, issue.12, pp.3247-3255, 2012.
DOI : 10.1016/j.cor.2012.04.017

P. Erdös and A. Rényi, On random graphs. I, Publicationes Mathematicae, vol.6, p.290297, 1959.

U. Feige, M. T. Hajiaghayi, and J. R. Lee, Improved approximation algorithms for minimum-weight vertex separators, 37th Annual ACM Symposium on Theory of Computing (STOC), pp.563-572, 2005.

M. R. Fellows and M. A. Langston, On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design, SIAM Journal on Discrete Mathematics, vol.5, issue.1, pp.117-126, 1992.
DOI : 10.1137/0405010

V. Gogate and R. Dechter, A complete anytime algorithm for treewidth, Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI'04, pp.201-208, 2004.

J. Gustedt, On the pathwidth of chordal graphs, Discrete Applied Mathematics, vol.45, issue.3, pp.233-248, 1993.
DOI : 10.1016/0166-218X(93)90012-D

URL : https://hal.archives-ouvertes.fr/inria-00549556

A. Hein and A. M. Koster, An Experimental Evaluation of Treewidth at Most Four Reductions, 10th Int. Symposium on Experimental Algorithms (SEA), pp.218-229, 2011.
DOI : 10.1007/978-3-642-20662-7_19

P. Hunter and S. Kreutzer, Digraph measures: Kelly decompositions, games, and orderings, Theoretical Computer Science, vol.399, issue.3, pp.206-219, 2008.
DOI : 10.1016/j.tcs.2008.02.038

T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas, Directed Tree-Width, Journal of Combinatorial Theory, Series B, vol.82, issue.1, pp.138-154, 2001.
DOI : 10.1006/jctb.2000.2031

N. G. Kinnersley, The vertex separation number of a graph equals its path-width, Information Processing Letters, vol.42, issue.6, pp.345-350, 1992.
DOI : 10.1016/0020-0190(92)90234-M

L. M. Kirousis and C. H. Papadimitriou, Searching and pebbling, Theoretical Computer Science, vol.47, issue.3, pp.205-218, 1986.
DOI : 10.1016/0304-3975(86)90146-5

K. Kitsunai, Y. Kobayashi, K. Komuro, H. Tamaki, and T. Tano, Computing Directed Pathwidth in O(1.89 n ) Time, International Symposium on Parameterized and Exact Computation (IPEC), pp.182-193, 2012.
DOI : 10.1007/978-3-642-33293-7_18

T. Kloks, H. L. Bodlaender, H. Müller, and D. Kratsch, Computing treewidth and minimum fillin: All you need are the minimal separators, First Annual European Symposium on Algorithms (ESA), pp.260-271, 1993.

Y. Kobayashi, K. Komuro, and H. Tamaki, Search Space Reduction through Commitments in Pathwidth Computation: An Experimental Study, 13th International Symposium on Experimental Algorithms (SEA), pp.388-399, 2014.
DOI : 10.1007/978-3-319-07959-2_33

N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM, vol.35, issue.1, pp.18-44, 1988.
DOI : 10.1145/42267.42268

B. Monien and I. H. Sudborough, Min cut is NP-complete for edge weighted trees, Theoretical Computer Science, vol.58, issue.1-3, pp.209-229, 1988.
DOI : 10.1016/0304-3975(88)90028-X

B. A. Reed, Finding approximate separators and computing tree width quickly, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , STOC '92, pp.221-228, 1992.
DOI : 10.1145/129712.129734

N. Robertson and P. D. Seymour, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, vol.35, issue.1, pp.39-61, 1983.
DOI : 10.1016/0095-8956(83)90079-5

N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, vol.7, issue.3, pp.309-322, 1986.
DOI : 10.1016/0196-6774(86)90023-4

URL : http://doi.org/10.1006/jctb.1999.1919

H. Röhrig, Tree decomposition: a feasibility study, 1998.

J. Sánchez-oro, J. J. Pantrigo, and A. Duarte, Combining intensification and diversification strategies in VNS. An application to the Vertex Separation problem, Computers & Operations Research, vol.52, pp.209-219, 2014.
DOI : 10.1016/j.cor.2013.11.008

P. D. Seymour and R. Thomas, Call routing and the ratcatcher, Combinatorica, vol.32, issue.2, pp.217-241, 1994.
DOI : 10.1007/BF01215352

K. Skodinis, Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time, Journal of Algorithms, vol.47, issue.1, pp.40-59, 2003.
DOI : 10.1016/S0196-6774(02)00225-0

F. Solano, Analyzing two different objectives of the WDM network reconfiguration problem, Proc. IEEE Globecom, pp.1-7, 2009.

F. Solano and M. Pióro, Lightpath Reconfiguration in WDM Networks, Journal of Optical Communications and Networking, vol.2, issue.12, pp.1010-1021, 2010.
DOI : 10.1364/JOCN.2.001010

W. Stein, Sage Mathematical Software System (Version 6.6) The Sage Development Team, 2015.

K. Suchan and I. Todinca, Pathwidth of Circular-Arc Graphs, Proc. WG, pp.258-269, 2007.
DOI : 10.1007/978-3-540-74839-7_25

URL : https://hal.archives-ouvertes.fr/hal-00462302

K. Suchan and Y. Villanger, Computing Pathwidth Faster Than 2 n, 4th International Workshop on Parameterized and Exact Computation (IWPEC), pp.324-335, 2009.
DOI : 10.1007/978-3-642-11269-0_27

M. E. Van-boxel, Improved algorithms for the computation of special junction trees, 2014.

J. Van-den-broek and H. Bodlaender, TreewidthLIB, a benchmark for algorithms for treewidth and related graph problems

B. Yang and Y. Cao, Digraph searching, directed vertex separation and directed pathwidth, Discrete Applied Mathematics, vol.156, issue.10, pp.1822-1837, 2008.
DOI : 10.1016/j.dam.2007.08.045

B. Yang and Y. Cao, Monotonicity in digraph search problems, Theoretical Computer Science, vol.407, issue.1-3, pp.532-544, 2008.
DOI : 10.1016/j.tcs.2008.08.025