Samuel Kroger

A polytime preprocess algorithm for the maximum independent set problem

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Graphs and Matroids

    The maximum independent set (MIS) seeks to find a subset of vertices with the maximum size such that no pair of its vertices are adjacent. This paper develops a recursive fixing procedure that generalizes the existing polytime algorithm to solve the maximum independent set problem on chordal graphs, which admit simplicial orderings. We prove that … Read more

    Maximizing resilience in large-scale social networks

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    Motivated by the importance of social resilience as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph G=(V,E) and integers k and b, the maximum anchored k-core problem seeks to find a largest … Read more