On the Minimum Chordal Completion Polytope

References

• Agrawal A, Klein P, Ravi R (1993) Cutting down on fill using nested dissection: Provably good elimination orderings. George A, Gilber JR, Liu JWH, eds. Graph Theory and Sparse Matrix Computation (Springer, New York), 31–55.Crossref, Google Scholar
• Beeri C, Fagin R, Maier D, Yannakakis M (1983) On the desirability of acyclic database schemes. J. ACM. 30(3):479–513.Crossref, Google Scholar
• Bergman D, Raghunathan AU (2015) A Benders approach to the minimum chordal completion problem. Pesant G, ed. Principles and Practice of Constraint Programming—CP 2015, Lecture Notes in Computer Science, vol. 6308 (Springer, Berlin), 47–64.Crossref, Google Scholar
• Berry A, Bordat JP, Heggernes P, Simonet G, Villanger Y (2006) A wide-range algorithm for minimal triangulation from an arbitrary ordering. J. Algorithms 58(1):33–66.Crossref, Google Scholar
• Berry A, Heggernes P, Simonet G (2003) The minimum degree heuristic and the minimal triangulation process. Bodlaender H, ed. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2880 (Springer, Berlin), 58–70.Crossref, Google Scholar
• Bliznets I, Cygan M, Komosa P, Mach L, Pilipczuk M (2016) Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1132–1151.Crossref, Google Scholar
• Bouchitté V, Todinca I (2001) Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31(1):212–232.Crossref, Google Scholar
• Cao Y, Marx D (2016) Chordal editing is fixed-parameter tractable. Algorithmica 75(1):118–137.Crossref, Google Scholar
• Cao Y, Sandeep RB (2016) Minimum fill-in: Inapproximability and almost tight lower bounds. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 875–880.Google Scholar
• Chang MS (1996) Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. Asano T, Igarashi Y, Nagamochi H, Miyano S, Suri S, eds. Algorithms and Computation, Lecture Notes in Computer Science, vol. 1178 (Springer, Berlin), 146–155.Crossref, Google Scholar
• Chung F, Mumford D (1994) Chordal completions of planar graphs. J. Combin. Theory Ser. B. 62(1):96–106.Crossref, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Feremans C, Oswald M, Reinelt G (2002) A y-formulation for the treewidth. Technical report, Heidelberg University, Heidelberg, Germany.Google Scholar
• Fomin FV, Philip G, Villanger Y (2013) Minimum fill-in of sparse graphs: Kernelization and approximation. Algorithmica 71(1):1–20.Crossref, Google Scholar
• Fomin FV, Villanger Y (2012) Subexponential parameterized algorithm for minimum fill-in. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1737–1746.Crossref, Google Scholar
• Fulkerson DR, Gross OA (1965) Incidence matrices and interval graphs. Pacific J. Math. 15(3):835–855.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• George A, Liu WH (1989) The evolution of the minimum degree ordering algorithm. SIAM Rev. 31(1):1–19.Crossref, Google Scholar
• Grone R, Johnson CR, Sá EM, Wolkowicz H (1984) Positive definite completions of partial hermitian matrices. Linear Algebra Appl. 58(0):109–124.Crossref, Google Scholar
• Heggernes P (2006) Minimal triangulations of graphs: A survey. Discrete Math. 306(3):297–317.Crossref, Google Scholar
• IBM ILOG (2017) CPLEX Optimization Studio 12.7.1 User Manual (IBM ILOG, New York).Google Scholar
• Judd S, Kearns M, Vorobeychik Y (2011) Behavioral conflict and fairness in social networks. Chen N, Elkind E, Koutsoupias E, eds. Internet and Network Economics, Lecture Notes in Computer Science, vol. 7090 (Springer, New York), 242–253.Crossref, Google Scholar
• Kaplan H, Shamir R, Tarjan RE (1999) Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28(5):1906–1922.Crossref, Google Scholar
• Kim S, Kojima M, Mevissen M, Yamashita M (2011) Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Math. Programming 129(1):33–68.Crossref, Google Scholar
• Kloks T, Bodlaender H, Müller H, Kratsch D (1993) Computing Treewidth and Minimum Fill-In: All You Need Are the Minimal Separators (Springer, Berlin), 260–271.Google Scholar
• Kloks T, Kratsch D, Müller H (1999) Approximating the bandwidth for asteroidal triple-free graphs. J. Algorithms 32(1):41–57.Crossref, Google Scholar
• Kloks T, Kratsch D, Wong C (1998) Minimum fill-in on circle and circular-arc graphs. J. Algorithms 28(2):272–289.Crossref, Google Scholar
• Kratsch D, Müller H (2009) On a property of minimal triangulations. Discrete Math 309(6):1724–1729.Crossref, Google Scholar
• Lauritzen SL, Spiegelhalter DJ (1990) Local computations with probabilities on graphical structures and their application to expert systems. Shafer G, Pearl J, eds. Readings in Uncertain Reasoning (Morgan Kaufmann Publishers Inc., San Francisco), 415–448.Google Scholar
• Mezzini M, Moscarini M (2010) Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network. Theoret. Comput. Sci. 411(7–9):958–966.Crossref, Google Scholar
• Nakata K, Fujisawa K, Fukuda M, Kojima M, Murota K (2003) Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results. Math. Programming 95(2):303–327.Crossref, Google Scholar
• Natanzon A, Shamir R, Sharan R (2000) A polynomial approximation algorithm for the minimum fill-in problem. SIAM J. Comput. 30(4):1067–1079.Crossref, Google Scholar
• Nikolaou C, Koubarakis M (2014) Fast consistency checking of very large real-world RCC-8 constraint networks using graph partitioning. Proc. 28th AAAI Conf. A.I. (Association for the Advancement of Artificial Intelligence, Menlo Park, CA), 2724–2730.Google Scholar
• Nikolopoulos SD, Palios L (2007) Detecting holes and antiholes in graphs. Algorithmica 47(2):119–138.Crossref, Google Scholar
• Ohtsuki T (1976) A fast algorithm for finding an optimal ordering for vertex elimination on a graph. SIAM J. Comput. 5(1):133–145.Crossref, Google Scholar
• Ohtsuki T, Cheung LK, Fujisawa T (1976) Minimal triangulation of a graph and optimal pivoting order in a sparse matrix. J. Math. Anal. Appl. 54(3):622–633.Crossref, Google Scholar
• Parra A, Scheffler P (1995) How to use the minimal separators of a graph for its chordal triangulation. Fülöp Z, Gécseg F, eds. Automata, Languages and Programming—ICALP 1995, Lecture Notes in Computer Science, vol. 944 (Springer, Berlin), 123–134.Crossref, Google Scholar
• Parra A, Scheffler P (1997) Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math. 79(1):171–188.Crossref, Google Scholar
• Parter S (1961) The use of linear graphs in gauss elimination. SIAM Rev. 3(2):119–130.Crossref, Google Scholar
• Renz J (2002) The region connection calculus. Qualitative Spatial Reasoning with Topological Information (Springer, Berlin), 41–50.Crossref, Google Scholar
• Rollon E, Larrosa J (2011) On mini-buckets and the min-fill elimination ordering. Lee J, ed. Principles and Practice of Constraint Programming (CP) (Springer, Berlin), 759–773.Crossref, Google Scholar
• Rose DJ (1972) A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Read RC, ed. Graph Theory and Computing (Academic Press, Cambridge, MA), 183–217.Crossref, Google Scholar
• Rose DJ, Tarjan RE (1978) Algorithmic aspects of vertex elimination on directed graphs. SIAM J. Appl. Math. 34(1):176–197.Crossref, Google Scholar
• Rose DJ, Tarjan RE, Lueker GS (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2):266–283.Crossref, Google Scholar
• Rostami B, Malucelli F, Frey D, Buchheim C (2015) On the quadratic shortest path problem. Internat. Sympos. Experiment. Algorithms (Springer, New York), 379–390.Crossref, Google Scholar
• Sioutis M (2014) Triangulation versus graph partitioning for tackling large real world qualitative spatial networks. 2014 IEEE 26th Internat. Conf. Tools Artificial Intelligence (IEEE, Piscataway, NJ), 194–201.Crossref, Google Scholar
• Sioutis M, Koubarakis M (2012) Consistency of chordal rcc-8 networks. 2012 IEEE 24th Internat. Conf. Tools Artificial Intelligence, vol. 1 (IEEE, Piscataway, NJ), 436–443.Crossref, Google Scholar
• Tarjan RE, Yannakakis M (1984) Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3):566–579.Crossref, Google Scholar
• Uno T, Satoh H (2014) An efficient algorithm for enumerating chordless cycles and chordless paths. Internat. Conf. Discovery Sci. (Springer, New York), 313–324.Crossref, Google Scholar
• Vandenberghe L, Andersen MS (2015) Chordal graphs and semidefinite optimization. Foundations Trends Optim. 1(4):241–433.Crossref, Google Scholar
• Yannakakis M (1981) Computing the minimum fill-in is NP-Complete. SIAM J. Algebraic Discrete Methods 2(1):77–79.Crossref, Google Scholar
• Yüceoğlu B (2015) Branch-and-cut algorithms for graph problems. Unpublished doctoral thesis, Maastricht University, Mastricht, Netherlands.Google Scholar
• Zhang C, Zhao T, Li W (2015) Ontology Data Query in Geospatial Semantic Web (Springer International Publishing, Cham, Switzerland), 57–87.Crossref, Google Scholar