Parameterized aspects of strong subgraph closure

DOI10.4230/LIPICS.SWAT.2018.23MaRDI QIDQ5116487zbMATH OpenFDO

Authors Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Charis Papadopoulos, Paloma T. Lima

Publication date 25 August 2020

zbMATH Keywords

parameterized complexityforbidden subgraphsstrong triadic closure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized aspects of strong subgraph closure
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Maximizing the strong triadic closure in split graphs and proper interval graphs

Cites work

• Designing FPT algorithms for cut problems using randomized contractions
• Edge-Deletion Problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Incompressibility of \(H\)-free edge modification problems
• Kernelization lower bounds through colors and IDs
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Networks, crowds and markets. Reasoning about a highly connected world.
• On problems without polynomial kernels
• Parameterized algorithms
• Parameterized complexity of finding subgraphs with hereditary properties.
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Solving MAX-\(r\)-SAT above a tight lower bound
• Sparsity. Graphs, structures, and algorithms
• Strong triadic closure in cographs and graphs of low maximum degree
• Two edge modification problems without polynomial kernels

Cited in

(5)

• Essentially tight kernels for (weakly) closed graphs
• Essentially tight kernels for (weakly) closed graphs
• Cluster deletion on interval graphs and split related graphs
• Parameterized aspects of strong subgraph closure
• Detecting and enumerating small induced subgraphs in c-closed graphs

This page was built for publication: Parameterized aspects of strong subgraph closure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116487)