by Oleg Shcherbina and Arnold Neumaier
University of Vienna
Most large-scale problems have a sparse structure described by a (sometimes very large) graph. In generalization of the multifrontal approach to solving sparse linear systems of equations, one may solve many other classes of large-scale problems by means of a so-called tree decomposition of their associated graph. A tree decomposition gives rise to a covering of the edges of the graph by a small sets of fronts whose intersection structure is described by a so-called join tree. The join tree structure enables many otherwise NP-hard problems to be solved in time proportional to the number of fronts, provided that the associated subproblems on each front can be solved in constant time.
This page is a collection of links to papers and web sites on material related to multifrontal techniques. (Pointers to additional work are appreciated.) It contains sections on
A. Berry, J.-P. Bordat, and O. Cogis, Generating all the minimal separators of a graph , Int. J. Found. Comput. Sci., 11 (2000), 397-403.
S. Friedland, On the graph isomorphism problem, Manuscript (2008).
R.E. Tarjan and M. Yannakakis, Simple linear-time algorithm to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs , SIAM J. Computing 13 (1984), 566-579.
J. Tor\'an, Reductions to Graph Isomorphism , pp. 158--167 in: Lecture Notes in Computer Science, Vol. 4855, Springer, Berlin 2007.
R. Dechter, Y. El Fattah, Topological parameters for time-space tradeoff, Artif. Intell. 125 (2001), 93-118.
R. Dechter, J. Pearl, Tree clustering for constraint networks, Artif. Intell. 38 (1989), 353-366.
J.W.H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review 34 (1992), 82-109.
C.J. Alpert, S.Z. Yao, Spectral partitioning: the more eigenvectors, the better. In: 32th DAC, ACM/IEEE, 195-200 (1995).
E.G. Boman, D. Bozdag, U.V. Catalyurek, K.D. Devine, A.H. Gebremedhin, P.D. Hovland, A. Pothen, and M.M. Strout, Enabling high performance computational science through combinatorial algorithms, Proceedings of SciDAC 2007, Journal of Physics: Conference Series 78 (2007) 012058, August 2007.
J. Falkner, F. Rendl, H. Wolkowicz, A computational study of graph partitioning, Math. Programming 66 (1994), 211-239.
C.M. Fiduccia, R.M. Mattheyses, A linear-time heuristics for improving network partitions. pp. 175-181 in: Proc. 19th ACM/IEEE Design Automation Conference, (1982).
G.W. Flake, R.E. Tarjan, K. Tsioutsiouliklis, Graph clustering and minimum cut trees, Internet Mathematics 1 (2003), 385-408.
A. Gebremedhin, F. Manne, A. Pothen, What color is your Jacobian? Graph coloring for computing derivatives, SIAM Review 47 (2005), 629-705.
A. Gebremedhin, A. Tarafdar, F. Manne, A. Pothen, New acyclic and star coloring algorithms with application to computing Hessians, SIAM J. Sci. Comput. 29 (2007), 1042-1072
R.E. Gomory, T.C. Hu, Multi-terminal network flows, SIAM J. on Applied Mathematics 9 (1961), 551-570.
A. Gupta, Fast and effective algorithms for graph partitioning and sparse matrix ordering, IBM J. Res. Development 41 (1997), 171-184.
B. Hendrickson and A. Pothen, Combinatorial Scientific Computing: The enabling power of discrete algorithms in computational science, Proceedings of the 7th International Meeting on High Performance Computing for Computational Science (VECPAR'06), Lecture Notes in Computer Science, Springer Verlag, 21 pp., 2006.
B. Hendrickson, R. Leland, A multilevel algorithm for partitioning graphs, In: Proc. Supercomputing '95, ACM, San-Diego, 1995.
JOSTLE -- graph partitioning software.
G. Karypis, V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs. Tech. Rep. TR95-035. University of Minnesota, Minneapolis, 1995.
G. Karypis, V. Kumar, MeTiS -- a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. Version 4, University of Minnesota, 1998.
R. Preis and R. Diekmann, Party -- a software library for graph partitioning, In: B.H.V. Topping (ed.) Advances in Computational Mechanics with Parallel and Distributed Processing, pp.63-71, 1997.
H.D. Simon, Partitioning of unstructured problems for parallel processing, Computing Systems in Engineering 2 (1991), 135-148.
A. Dermaku, T. Ganzow, G. Gottlob, B. McMahan, N. Musliu, M. Samer, Heuristic methods for hypertree decompositions. DBAI Techn. Report DBAI-TR-2005-53. Technische Universitaet Wien, Vienna (2005).
G. Gottlob, N. Leone, F. Scarcello, A comparison of structural CSP decomposition methods, Artificial Intelligence 124 (2000), 243-282.
G. Gottlob, N. Leone, F. Scarcello, Hypertree decompositions: A survey, pp. 37-57 in: Mathematical foundations of computer science. 26th international symposium, MFCS 2001. Proceedings. Springer, Berlin, Lect. Notes Comput. Sci. 2136, 2001.
G. Karypis, R. Aggarwal, V. Kumar, S. Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Trans. Very Large Scale Integr. Syst. 7 (1999), 69-79.
PaToH Partitioning Tools for Hypergraph.
M. Samer, Hypertree decomposition via branch-decomposition, pp. 1535-1536 in: International Joint conference of Artificial Intelligence (IJCAI05), 2005.
K. Grant and M.C. Horsch, Methods for Constructing Balanced Elimination Trees and Other Recursive Decompositions, Manuscript (2005).
E. Loute, Gaussian elimination as a computational paradigm. Core discussion paper 2003/59.
A. Natanzon, R. Shamir and R. Sharan, A polynomial approximation algorithm for the minimum fill-in problem, pp. 41-47 in: Proc. 30th Ann. ACM Symp. on Theory of Comp., ACM 1998.
S. Parter, The use of linear graphs in Gauss elimination, SIAM Review 3 (1961), 119-130.
D. Rose, R. Tarjan, G. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing 5 (1976), 266-283.
M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Alg. Discr. Meth. 2 (1981), 77-79.
P.R. Amestoy, T.A. Davis, I.S. Duff, An approximate minimum degree ordering algorithm. SIAM J Matrix Anal. Appl. 17 (1996), 886-905.
C. Ashcraft, Compressed graphs and the minimum degree algorithm, SIAM J. Sci. Comput. 16 (1995), 1404-1411.
C. Ashcraft, J.W.H. Liu, Robust ordering of sparse matrices using multisection, SIAM J. Matrix Anal. Appl. 19 (1998), 816-832.
T.A. Davis, P. Amestoy and I.S. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl. 17 (1996), 886-905.
P. Heggernes, S.C. Eisenstat, G. Kumfert, A. Pothen, The Computational Complexity of the Minimum Degree Algorithm. Techn. report UCRL-ID-148375. Lawrence Livermore National Laboratory (2001).
A. George and J.W.H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Rev. 31 (1989),pp. 1-19.
A. George, J.W. Poole, and R.Voigt, Incomplete nested dissection for solving $n$ by $n$ grid problems, SIAM J. Numer. Anal. 15 (1978), 663-673.
A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal. 10 (1973), pp. 345-363.
A. George and J.W.H. Liu, A fast implementation of the minimum degree algorithm using quotient graphs, ACM Trans. Math. Software 6 (1980), 337-358.
S.I. Larimore, An approximate minimum degree column ordering algorithm, MS Thesis, Dept. of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, 1998.
R.J. Lipton, D.J. Rose, R.E. Tarjan, Generalized nested dissection, SIAM J. of Numerical Analysis 16(2) (1979), 346-358.
J.W.H. Liu, The minimum degree ordering with constraints, SIAM J. Sci. Comput. 10 (1989), pp. 1136-1145.
F. Pellegrini, J. Roman, P. Amestoy, Hybridizing nested dissection and halo approximate degree for efficient sparse matrix ordering, Lecture Notes in Computer Science 1586, Springer, Berlin 1999, pp. 986-995.
F. Pellegrini, J. Roman, and P. R. Amestoy. Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering. Concurrency: Practice and Experience, 12:69-84, 2000.
E. Amir, Efficient approximation for triangulation of minimum treewidth. Uncertainty in Artificial Intelligence (2001), 7-15.
S. Arnborg, D.G. Corneil and A. Proskurowski, Complexity of finding embeddings in a $k$-tree, SIAM J. Alg. Discr. Meth. 8 (1987), 277-284.
S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial $k$-trees, Discrete Applied Mathematics 23 (1989), 11-24.
S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, J. of Alg. 12 (1991), 308-340.
S. Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded decomposability -- a survey, BIT Numerical Mathematics 25 (1985), 1-23.
S. Arnborg and A. Proskurowski, Characterization and Recognition of Partial k-trees, SIAM J. Alg. Discr. Meth. 7 (1986), 305-314.
E.H. Bachoore and H.L. Bodlaender, New Upper Bound Heuristics for Treewidth, pp. 216-227 in: Lecture notes in computer science , Vol. 3503, Springer, Berlin 2005.
A. Becker, D. Geiger, A sufficiently fast algorithm for finding close to optimal clique trees. Artificial Intelligence 125 (2001), 3-17.
A. Becker and D. Geiger, A sufficiently fast algorithm for finding close to optimal junction trees, pp. 81-89 in: Uncertainty in AI (UAI'96), 1996.
A. Berry, A wide-range efficient algorithm for minimal triangulation. In: Proceedings of SODA, (1999).
J.R.S. Blair and B.W. Peyton, An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computation. 1-29. Springer, New York (1993).
J.R.S. Blair and B.W. Peyton, On Finding Minimum-Diameter Clique Trees, Nordic J. Computing, 1 (1994), 173-201.
H.L. Bodlaender, Treewidth: Algorithmic techniques and results, pp. 19-36 in: Privara L et al.(eds) Mathematical foundations of computer science. 22nd international symposium, MFCS '97, Bratislava, Slovakia, August 25-29, 1997. Proceedings. Lect. Notes Comput. Sci. 1295. Springer, Berlin (1997)
H.L. Bodlaender, Discovering Treewidth, pp. 1-16 in: Proceedings of SOFSEM Springer-Verlag, LNCS 3381. 2006.
H. Bodlaender, A.M.C.A. Koster, Combinatorial optimization on graphs of bounded treewidth, Computer Journal 51 (2008), 255-269.
H. Bodlaender, A.M.C.A. Koster, F. van den Eijkhof, and L.C. van der Gaag, Pre-processing for Triangulation of Probabilistic Networks, pp. 32-39 in: Proc. 17th Conf. Uncertainty in Artificial Intelligence, Morgan Kaufmann, 2001.
H.L. Bodlaender, Treewidth: Characterizations, Applications, and Computations, technical report UU-CS-2006-041,Department of Information and Computing Sciences, Utrecht University.
V. Bouchitt\'e, D. Kratsch, H. Muller, I. Todinca, On treewidth approximations, Discrete Appl. Math. 136 (2004), 183-196.
A. Cano and S. Moral, Heuristic Algorithms for the Triangulation of Graphs, pp. 98-107 in: Lecture Notes In Computer Science; Vol. 945, Springer 1994.
W. Cook, P.D. Seymour, Tour merging via branch-decomposition, INFORMS Journal on Computing 15 (2003),233-248.
P.A. Dow and R.E. Korf, Best-first search for treewidth, Proc. 22nd Conf. Artificial Intelligence (AAAI-2007), Vancouver, British Columbia, July 2007.
F. Fomin, D. Kratsch, I. Todinca, Exact (exponential) algorithms for treewidth and minimum fill-in, pp. 568-580 in: Proceedings of ICALP, (2004).
V. Gogate, R. Dechter, A complete anytime algorithm for treewidth. In: Proceedings of UAI (2004), 201-208.
P. Heggernes, Minimal triangulations of graphs: A survey, Discrete Mathematics 306 (2006), 297-317.
I.V. Hicks, A.M.C.A. Koster, E. Kolotoglu, Branch and Tree Decomposition Techniques for Discrete Optimization. In: Tutorials in Operations Research. New Orleans: INFORMS, 2005, 1–29.
K. Kask, R. Dechter, J. Larrosa, A. Dechter, Unifying cluster-tree decompositions for reasoning in graphical models, Artif. Intell. 160 (2005), 165-193.
U. Kjaerulff, Triangulation of graphs - algorithms giving small total state space, Tech. Report, Aalborg, Denmark, 1990.
A.M.C.A. Koster, C.P.M. van Hoesel, A.W.J. Kolen, Solving frequency assignment problems via tree-decomposition. In: Broersma, H.J. et al.(eds.). 6th Twente workshop on graphs and combinatorial optimization. Univ. of Twente, Enschede, Netherlands, May 26-28, 1999.
A.M. Koster, H L. Bodlaender, and S.P.M. van Hoesel, Treewidth: computational experiments. Techn. Report 01-38, Berlin, Germany, 2001.
O.A. Shcherbina, Tree decomposition and discrete optimization problems: a survey, Cybernetics and system analysis 43 (2007), 549-562.
K. Shoikhet, D. Geiger, A practical algorithm for finding optimal triangulation, pp. 185-190 in: Proceedings of AAAI (1997).
T. Wolle, Computational aspects of Treewidth, lower bounds and networks reliability. Dissertation: UU Universiteit Utrecht (2005).
Y.E. Campbell, T.A. Davis, Computing the sparse inverse subset an inverse multifrontal approach, Technical Report TR-95-021, Computer and Information Sciences Department, University of Florida, Gainesville, October, 1995.
IAIN S. DUFF. A Survey of Sparse Matrix Research, PROCEEDINGS OF THE IEEE, VOL. 65 , N 4, 1977, p. 500-535.
A.M. Erisman, W. F. Tinney, On computing certain elements of the inverse of a sparse matrix, Comm. ACM 18 (1975), 177-179.
M. Fukuda, M. Kojima, K. Murota, and K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: general framework, SIAM J. Optimization 11 (2000), 647-674.
A. George and J.W.H. Liu, Algorithms for matrix partitioning and the numerical solution of finite element systems, SIAM J. Numer. Anal. 15 (1978), 293-327. P> A. George and J.W.H. Liu, A quotient graph model for symmetric factorization, In: I.S.Duff and G.W.Stewart (eds.), Sparse Matrix Proceedings, SIAM Publications, 1978, 154-175.
N.I.M. Gould, J.A. Scott, and Y. Hu, A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations, ACM Trans. Math. Software 33 (2007), No. 10, B1-B32.
R. Grone, C.R. Johnson, E.M. S\'a, and H. Wolkowicz, Positive definite completions of partial Hermitian matrices, Linear Algebra and Appl., 58 (1984), 109-124.
A. Gupta, G. Karypis and V. Kumar, Highly scalable parallel algorithms for sparse matrix ordering, IEEE Transactions on Parallel and Distributed Systems, 1994.
B. Hendrickson, R. Leland, The Chaco user's guide. Version 2.0. Technical Report SAND95-2344, Sandia National Laboratories, 1995.
J.W.H. Liu, E.G. Ng, and B.W. Peyton, On finding supernodes for sparse matrix computations, SIAM J. Matrix Anal. Appl. 14 (1993), 242-252.
J.W.H. Liu, Equivalent sparse matrix reordering by elimination tree rotations, SIAM J. Sci. Comput. 9 (1988), 424-444.
J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11 (1990), 134-172.
K. Nakata, K. Fujitsawa, M. Fukuda, M. Kojima, and K. Murota, Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical details, Mathematical Programming Series B, 95 (2003), 303-327.
H. Niessner, K. Reichert, On computing the inverse of a sparse matrix, International Journal for Numerical Methods in Engineering 19 (1983), 1513-1526.
F. Pellegrini, J. Roman, Sparse matrix ordering with SCOTCH. In: Proc. of HPCN'97, Vienna, LNCS 1225, 370-378 (1997).
A. Pothen, H. Simon, K. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl. 11 (1990), 430-452.
SPOOLES 2.2 : SParse Object Oriented Linear Equations Solver
M.M. Strout, L. Carter, J. Ferrante, J. Freeman, B. Kreaseck, Combining performance aspects of irregular Gauss-Seidel via sparse tiling, In: Proc. of the 15th Workshop on Languages and Compilers for Parallel Computing, College Park MD 2002.
S. Vavasis, A note on efficient computation of the gradient in semidefinite programming.
R. Dechter, Bucket Elimination: a Unifying Framework for Reasoning, Artificial Intelligence 113 (1999), 41-85.
R. Giegerich and C. Meyer, Algebraic dynamic programming , In H. Kirchner and C. Ringeissen, eds, Algebraic Methodology And Software Technology, pages 349-364. LNCS 2422, 2002, Springer-Verlag
J. Hooker, Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Wiley, New York 2000.
J.N. Hooker, Logic, optimization and constraint programming, INFORMS Journal on Computing 14 (2002), 295-321.
L. Huang, Dynamic programming algorithms in semiring and hypergraph frameworks
L. Huang, D. Chiang, Better $k$-best parsing, Proc. 9th Int. Workshop Parsing Technologies (IWPT), pp. 53-64, Vancouver, October 2005.
M. Pouly and J. Kohlas, Dynamic Programming \& Local Computation, Manuscript (2007)
A. Rosenthal, Dynamic programming is optimal for nonserial optimization problems, SIAM J. Comput. 11 (1982), 47-59.
O.A. Shcherbina, Local elimination algorithms for solving sparse discrete problems, Computational Mathematics and Mathematical Physics 48 (2008), 152-167.
P.P. Shenoy, Valuation-based systems for Bayesian decision analysis, Operations Research 40 (1992), 463-484.
P.P. Shenoy, Axioms for Dynamic Programming, pp. 259-275 in: Computational Learning and Probabilistic Reasoning (A. Gammerman, ed.), Wiley, Chichester 1996.
C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, On the desirability of acyclic database schemes, J. ACM 30 (1983), 479-513.
M. Gyssens, P.G. Jeavons, D.A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artif. Intell. 66 (1994), 57-89.
P.A. Bernstein and N. Goodman, Powers of natural semijoins, SIAM J. Comput. 10 (1981), 751-771.
M. Yannakakis, Algorithms for acyclic database schemes, pp. 82-94 in: C. Zaniolo, C. Delobel (Eds.), Proc. Internat. Conference on Very Large Data Bases (VLDB-81), Cannes, France, 1981.
R.G. Almond, Graphical Belief Modeling, Chapman and Hall, London 1995.
I. Arad, Z. Landau, Quantum computation and the evaluation of tensor networks, arXiv:0805.0040 (May 2008).
O. Banerjee, A. d'Aspremont, L. El Ghaoui, Sparse covariance selection via robust maximum likelihood estimation, arXiv:cs/0506023v1
O. Banerjee, L.E. Ghaoui, A. d'Aspremont, and G. Natsoulis, Convex optimization techniques for fitting sparse Gaussian graphical models, In: Proceedings of the 23rd international Conference on Machine Learning (Pittsburgh, Pennsylvania, June 25-29, 2006). ICML '06, vol. 148 (2006). ACM, New York, NY, 89-96.
T. Berger and Z. Ye, Entropic aspects of random fields on trees, IEEE Trans. Information Theory 36 (1990), 1006-1018.
M. Van den Nest, W. Duer, G. Vidal, and H.J. Briegel, Classical simulation versus universality in measurement-based quantum computation, Physical Review A 75 (2007), 012337: 1-15.
L. Cincio, J. Dziarmaga, and M.M. Rams, Multiscale Entanglement Renormalization Ansatz in Two Dimensions: Quantum Ising Model, Phys. Rev. Lett. 100, 240603 (2008).
R. Dahlhaus, Graphical interaction models for multivariate time series, Metrika, 51 (2000), 157-172.
J. Dahl, L. Vandenberghe, V. Roychowdhury, Covariance selection for non-chordal graphs via chordal embedding, Optimization Methods and Software (2008) (to appear).
M. Drton, M.D. Perlman, A SINful approach to Gaussian graphical model selection, Journal of Statistical Planning and Inference 138 (2008), 1179-1200.
W.J. Ewens and N.C.E. Shute, A resolution of the ascertainment sampling problem. I. Theory. Theor Popul Biol 30 (1986), 388-412
M.J. Flores, Bayesian networks inference: Advanced algorithms for triangulation and partial abduction, Ph.D. Thesis, University de Castilla - La Mancha (2005).
HUGIN API Reference Manual, Version 6.7, Manuscript (2007).
J.K. Johnson, V. Chandrasekaran, and A.S. Willsky, Learning Markov structure by maximum entropy relaxation, 11th Inter. Conf. on AI and Stat. (AISTATS '07), San Juan, Puerto Rico, March 2007.
R. Jozsa, On the simulation of quantum circuits, arXiv:quant-ph/0603163v1
S.L. Lauritzen and D.J. Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems, J. Roy. Stat. Soc. B 50 (1988), 205-247.
V. Lepar and P.P. Shenoy, A comparison of architectures for exact computation of marginals, Tech. Rep. 1997.
Z. Lu, Smooth optimization approach for covariance selection, SIAM J. Optimization, to appear.
I.L. Markov, Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM J. Comput. 38 (2008), 963-981.
J. Moussouris, Gibbs and Markov random systems with constraints, J. Stat. Phys. 10 (1974), 11-33.
A. Neumaier, E. Groeneveld, Restricted maximum likelihood estimation of covariances in sparse linear models, Genet. Sel. Evol. 30 (1998), 3-26.
A. Neumann, Statistical shape description using decomposable graphical models, in: University of the Federal Armed Forces Hamburg, Discussion Papers in Statistics and Quantitative Economics, No. 84, 1998.
D. Nilsson, An efficient algorithm for finding the $M$ most probable configurations in Bayesian networks, Statistics and Computing 8 (1998), 159-173.
D. Nilsson, J. Goldberger, Sequentially finding the $N$-best list in hidden Markov models, International Conference on Artificial Intelligence (IJCAI), 2001.
J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, pp. 133-136 in: D.L. Waltz (ed.), Proc. National Conf. Artificial Intelligence, AAAI Press, Menlo Park 1982.
J. Pearl, A constraint-propagation approach to probabilistic reasoning, pp. 357-370 in: L.N. Kanal and J.F. Lemmer (eds.), Uncertainty in Artificial Intelligence, North Holland, Amsterdam 1986.
J. Pearl, Graphical models, causality, and intervention, Statistical Science 8 (1993), 266-269.
A. Pelizzola, Cluster variation method in statistical physics and probabilistic graphical models, J. Phys. A: Math. Gen., 38 (2005), R309-R339.
Z. Rakamaric, C. Dabrowski, CS 532c - Probabilistic Graphical Models $N$-Best Hypotheses
A. Roverato, Prior distributions for Gaussian graphical models: a comparison between the directed and undirected case, Metron, 59 (2001), 205-216.
H. Rue, S. Martino, Approximate Inference for Hierarchical Gaussian Markov Random Fields Models, Preprint Statistics No. 7/2005 Norwegian University of Science and Technology, Trondheim, Norway, 2005.
H. Rue, S. Martino, Approximate Bayesian inference for hierarchical Gaussian Markov random field models, Journal of Statistical Planning and Inference 137 (2007) 3177 - 3192.
H. Rue, S. Martino, N. Chopin, Approximate Bayesian Inference for Latent Gaussian Models Using Integrated Nested Laplace Approximations, Technical report No. 1/2007, Department of Mathematical Sciences, Norwegian University of Science and Technology.
L.K. Saul and M.I. Jordan, Learning in Boltzmann trees, Neural Comput. 6 (1994), 1173-1183.
C. Schneuwly, M. Pouly, and J. Kohlas, Local Computation in Covering Join Trees. Tech. rept. 04-16. Department of Informatics, University of Fribourg (2004).
G. Shafer and P.P. Shenoy, Local computations in hypertrees, Manuscript of a book (1991).
O.A. Shcherbina, Tree decomposition and postoptimality analysis in discrete optimization (2009), arXiv:0903.4435v1 [cs.DM]
Y.-Y. Shi, L.-M. Duan, G. Vidal, Classical simulation of quantum many-body systems with a tree tensor network, Phys. Rev. A 74, 022320 (2006), quant-ph/0511070.
G. Vidal, A class of quantum many-body states that can be efficiently simulated, arXiv:quant-ph/0610099
G. Vidal, Entanglement Renormalization, Phys. Rev. Lett. 99, 220405 (2007), cond-mat/0512165
N. Wermuth, Linear recursive equations, covariance selection, and path analysis, Journal of the American Statistical Association, 75(372) (1980), 963-972.
S. Bistarelli, U. Montanari, and F. Rossi, Semiring-based constraint satisfaction and optimization, Journal of the ACM, 44 (1997), 201-236.
H. Chen, Quantified constraint satisfaction and bounded treewidth, in: Proceedings of ECAI-04, 2004, pp. 161-165.
R. Dechter , and J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence 34 (1987), 1-38.
R. Dechter, Tractable Structures for Constraint satisfaction problems
E.C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM) 29 (1982), 24-32.
A.Y. Grama, V. Kumar, A survey of parallel search algorithms for discrete optimization problems, ORSA Journal of Computing, 7(4)(1995), 365-85.
J. Gu, P.W. Purdom, J. Franco, B.W. Wah, Algorithms for the satisfiability (SAT) problem: A survey. pp. 19-153 in: Satisfiability Problem Theory and Applications, 1997.
P.G. Jeavons, M. Gyssens, D.A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artif. Intell., 66 (1994), 57-89.
P. J\'egou, S.N. Ndiaye, C. Terrioux, Computing and exploiting tree-decompositions for (Max-)CSP. In: Proc. 11th Int. Conf. Principles Practice Constraint Programming (CP-2005), 777-781 (2005).
J. Pearson, P. Jeavons, A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, Royal Holloway University of London, 1997.
E. Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993.
L.R. Nielsen, K.A. Andersen, D. Pretolani, Finding the $K$ Shortest Hyperpaths, Computers and Operations Research 32 (2005), 1477-1497.
L.R. Nielsen, D. Pretolani, K.A. Andersen, Finding the $K$ shortest hyperpaths using reoptimization, Operations Research Letters 34 (2006), 155-164.
Some of My Other Pages
Mathematical Software
Statistics Links
Computational Mathematics Links
Mathematics Links
FMathL - Formal mathematical language
Global Optimization
my
home page (http://arnold-neumaier.at)