Skip to content

Optimization Online

  • Welcome
  • Repository
  • Submit
  • About
  • Help
  • My Eprints

fpt

Kernels in planar digraphs

Published: 2004/06/18
  • Gregory Gutin
  • Ton Kloks
  • Chuan Min Lee
  • Anders Yeo
  • Categories Graphs and Matroids Tags digraphs, fpt, kernels

    A set $S$ of vertices in a digraph $D=(V,A)$ is a kernel if $S$ is independent and every vertex in $V-S$ has an out-neighbor in $S$. We show that there exist $O(n2^{19.1 \sqrt{k}}+n^4)$-time and $O(2^{19.1 \sqrt{k}} k^9 + n^2)$-time algorithms for checking whether a planar digraph $D$ of order $n$ has a kernel with at … Read more

    Log in


    Repository

    Author List

    Months

    Categories

    Keywords

    alternating direction method of multipliers approximation algorithms augmented lagrangian method bilevel optimization Branch-and-Bound branch-and-cut chance constraints column generation combinatorial optimization complexity conic optimization convex optimization cutting planes decomposition derivative-free optimization distributionally robust optimization duality dynamic programming first-order methods global convergence global optimization heuristics integer programming interior point methods large-scale optimization linear programming machine learning mixed-integer linear programming mixed-integer nonlinear programming mixed-integer programming multiobjective optimization nonconvex optimization nonlinear optimization nonlinear programming nonsmooth optimization optimal control optimization proximal point algorithm quadratic programming robust optimization semidefinite programming stochastic optimization stochastic programming trust-region methods unconstrained optimization

    © 2025 Optimization Online • Child Theme of GeneratePress
    For feedback or questions, contact optonline@wid.wisc.edu.