Heuristic and metaheuristic methods for computing graph treewidth
François Clautiaux; Aziz Moukrim; Stéphane Nègre[1]; Jacques Carlier
- [1] Laboratoire de Recherche en Informatique d’Amiens, INSSET, 48 rue Raspail, 02100 St Quentin, France
RAIRO - Operations Research - Recherche Opérationnelle (2004)
- Volume: 38, Issue: 1, page 13-26
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topReferences
top- [1] E. Aarts and J.K. Lenstra, Local Search in Combinatorial Optimization. Series in Discrete Mathematics and Optimization. John Wiley and Sons (1997). Zbl0869.00019MR1458630
- [2] R. Ahuja, O. Ergun, J. Orlin and A. Punnen, A survey on very large-scale neighborhood search techniques. Discrete Appl. Math. 123 (2002) 75-102. Zbl1014.68052MR1922331
- [3] S. Arnborg, D.G. Corneil and A. Proskurowski, Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth. 8 (1987) 277-284. Zbl0611.05022MR881187
- [4] S. Arnborg and A. Proskurowki, Characterisation and recognition of partial 3-trees. SIAM J. Alg. Disc. Meth. 7 (1986) 305-314. Zbl0597.05027MR830649
- [5] H. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25 (1996) 1305-1317. Zbl0864.68074MR1417901
- [6] J. Carlier and C. Lucet, A decomposition algorithm for network reliability evaluation. Discrete Appl. Math. 65 (1993) 141-156. Zbl0848.90058MR1380072
- [7] F. Clautiaux, J. Carlier, A. Moukrim and S. Nègre, New lower and upper bounds for graph treewidth. WEA 2003, Lect. Notes Comput. Sci. 2647 (2003) 70-80. Zbl1023.68645MR2051951
- [8] F. Gavril, Algorithms for minimum coloring, maximum clique, minimum coloring cliques and maximum independent set of a chordal graph. SIAM J. Comput. 1 (1972) 180-187. Zbl0227.05116MR327580
- [9] F. Glover and M. Laguna, Tabu search. Kluwer Academic Publishers (1998). Zbl0930.90083MR1665424
- [10] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). Zbl0541.05054MR562306
- [11] F. Jensen, S. Lauritzen and K. Olesen, Bayesian updating in causal probabilistic networks by local computations. Comput. Statist. Quaterly 4 (1990) 269-282. Zbl0715.68076MR1073446
- [12] D.S. Johnson and M.A. Trick, The Second DIMACS Implementation Challenge: NP-Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability. Series in Discrete Math. Theor. Comput. Sci. Amer. Math. Soc. (1993).
- [13] A. Koster, Frequency Assignment, Models and Algorithms. Ph.D. Thesis, Universiteit Maastricht (1999).
- [14] A. Koster, H. Bodlaender and S. van Hoesel, Treewidth: Computational experiments. Fund. Inform. 49 (2001) 301-312. MR2154596
- [15] C. Lucet, J.F. Manouvrier and J. Carlier, Evaluating network reliability and 2-edge-connected reliability in linear time for bounded pathwidth graphs. Algorithmica 27 (2000) 316-336. Zbl0971.68009MR1759753
- [16] C. Lucet, F. Mendes and A. Moukrim, Méthode de décomposition appliquée à la coloration de graphes, in ROADEF (2002).
- [17] N. Robertson and P. Seymour, Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7 (1986) 309-322. Zbl0611.05017MR855559
- [18] D. Rose, Triangulated graphs and the elimination process. J. Math. Anal. Appl. 32 (1970) 597-609. Zbl0216.02602MR270957
- [19] D. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, in Graph Theory and Computing, edited by R.C. Reed. Academic Press (1972) 183-217. Zbl0266.65028MR341833
- [20] D. Rose, R. Tarjan and G. Lueker, Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5 (1976) 146-160. Zbl0353.65019MR408312
- [21] R. Tarjan and M. Yannakakis, Simple linear-time algorithm to test chordality of graphs, test acyclicity of hypergraphs, and selectivity reduce acyclic hypergraphs. SIAM J. Comput. 13 (1984) 566-579. Zbl0545.68062MR749707