Detecting and enumerating small induced subgraphs in \(c\)-closed graphs

DOI10.1016/j.dam.2021.06.019zbMath1469.05077arXiv2007.12077OpenAlexW3185936233MaRDI QIDQ2043376

Tomohiro Koana, André Nichterlein

Publication date: 2 August 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.12077

zbMATH Keywords

combinatorial algorithmssubgraph enumerationFPT in Psubgraph detection

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems, Computing dense and sparse subgraphs of weakly closed graphs

Cites Work

• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• On graphs without a \(C_{4}\) or a diamond
• On the complexity of fixed parameter clique and dominating set
• Faster multi-witnesses for Boolean matrix multiplication
• Paw-free graphs
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Finding and listing induced paths and cycles
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Powers of tensors and fast matrix multiplication
• A Linear Recognition Algorithm for Cographs
• Finding a Minimum Circuit in a Graph
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• Finding Cliques in Social Networks: A New Distribution-Free Model
• Finding Four-Node Subgraphs in Triangle Time
• Parameterized aspects of triangle enumeration