, On the model-checking of monadic second-order formulas with edge set quantifications, Discrete Applied Mathematics, vol.160, issue.6, pp.866-887, 2012.
DOI : 10.1016/j.dam.2010.12.017
URL : https://hal.archives-ouvertes.fr/hal-00481735
, Disjoint paths in tournaments The directed subgraphs homeomorphism problem, Theoretical Computer Science, vol.10, issue.3, pp.111-121, 1980.
, Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs, SIAM Journal on Discrete Mathematics, vol.24, issue.1, pp.146-157, 2010.
DOI : 10.1137/070697781
, The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, vol.110
DOI : 10.1016/j.jctb.2014.07.003
, Local search: Is brute-force avoidable?, Journal of Computer and System Sciences, vol.78, issue.3 2, pp.707-719, 2012.
, The Parameterized Complexity of Local Search for TSP, More Refined, ISAAC, vol.2011, pp.614-623
, Searching the k-change neighborhood for TSP is W[1]-hard, Operations Research Letters, vol.36, issue.1, pp.31-36, 2008.
DOI : 10.1016/j.orl.2007.02.008
, Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
, Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
DOI : 10.1109/FOCS.2011.23
, is it possible to add at most k edges such that the resulting graph remains plane and has diameter at most k? If (G, k) is a yes instance of the above problem, and G ? is a minor of G, then (G ? , k) is also a yes instance of the same problem. From the meta-algorithmic consequence of the Graph Minors series, it follows that the above problem is fixed-parameter tractable, i.e., there exists an algorithm with running time f (k)n O(1) (see e.g. [1]). However, so far no such algorithm has been constructed. A possible approach is to use the fact that, if (G, k) is a yes instance, then G has treewidth bounded by some function of k. Then a dynamic programming algorithm for Planar Completion to Bounded Diameter on graphs of bound treewidth would result in the construction of the desired algorithm. More generally, how can we design bounded-treewidth dynamic-programming algorithms for planar completion problems? References 1
, Nonconstructive tools for proving polynomialtime decidability, Journal of the ACM, vol.35, issue.3, pp.727-739, 1988.
, A new proof for the weak-structure theorem with explicit constants:00] Rajesh Chitnis Approximability and fixed parameter algorithms: a new look Sang-Il Oum: Excluded vertex-minors for graphs of linear rank-width a most k Janos Makowski: Definability of numerical graph parameters and various notions of width, pp.0-10
, The k-disjoint paths problem in directed planar graphs Paul Bonsma: Surface split decompositions: fast dynamic programming over branch decompositions for graphs of bounded genus:30] Guy Kortsarz: Tools for multicoloring with applications to planar graphs and bounded treewidth graphs, :00] Iyad A. Kanj: What makes normalized weighted satisfiability tractable? [12:15] Lunch, pp.0-1030
, Giannopoulou: Exclusion theorems for immersions on surface embedded graphs Packing edge-disjoint odd S-cycles in 4-edge-connected graphs Frédéric Mazoit: Tree-width of hypergraphs and surface duality [12:15] Lunch Sudeshna Kolay The Institute of Mathematical Sciences ? Chennai, Stephan Kreutzer: An excluded grid theorem for digraphs with forbidden minors, pp.0-1030