\u65e5\u6642: 2021\u5e7412\u670810\u65e5(\u91d1) 13:00-15:00
\n\u4f1a\u5834: \u4eac\u90fd\u5927\u5b66 \u6570\u7406\u89e3\u6790\u7814\u7a76\u6240(RIMS) <\/p>\n
\u8b1b\u6f14\u8005: \u5c0f\u7a74 \u667a\u5927 \u6c0f\uff08\u30d9\u30eb\u30ea\u30f3\u5de5\u79d1\u5927\u5b66\uff09
\n\u984c\u76ee: Parameterized algorithms on (weakly) closed graphs
\n\u6982\u8981: For a graph G and one of its vertices v, let cl(v) = max |N(v) \u2229 N(u)|, where the maximum is over all vertices u not adjacent to v. We say that G is c-closed if cl(v) < c for every vertex v and weakly \u03b3-closed if every induced subgraph H of G contains a vertex v with cl(v) < \u03b3 in H. The closure (weak closure) of G is the smallest integer c (\u03b3) such that G is c-closed (weakly \u03b3-closed). Fox et al. [ICALP \u201918, SICOMP 20] recently introduced these parameters motivated by triadic closure—a phenomenon occurring in social networks that pairs of vertices with common vertices tend to be adjacent. We discuss parameterized algorithms for classical graph problems on (weakly) closed graphs such as:
\n– s-plex (a relaxation of Clique) is O*(2^\u03b3)-time solvable.
\n– Independent Set has a kernel with at most \u03b3k^2 vertices.
\n– Dominating Set has a kernel of size k^O(c).
\n– Induced Matching has kernels with at most O(c^7 k^8) vertices and at most k^O(\u03b3) vertices.<\/p>\n
The talk will be based on three joint works with Christian Komusiewicz and Frank Sommer:
\n– Exploiting c-Closure in Kernelization Algorithms for Graph Problems. ESA 2020.
\n– Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. ISAAC 2020.
\n– Essentially Tight Kernels for (Weakly) Closed Graphs. ISAAC 2021 (to appear).<\/p>\n","protected":false},"excerpt":{"rendered":"
\u65e5\u6642: 2021\u5e7412\u670810\u65e5(\u91d1) 13:00-15:00 \u4f1a\u5834: \u4eac\u90fd\u5927\u5b66 \u6570\u7406\u89e3\u6790\u7814\u7a76\u6240(RIMS) \u8b1b\u6f14\u8005: \u5c0f\u7a74 \u667a\u5927 \u6c0f\uff08\u30d9\u30eb\u30ea\u30f3\u5de5\u79d1\u5927\u5b66\uff09 \u984c\u76ee: Parameterized algorithms on ( … <\/p>\n