Enumerating connected induced subgraphs: improved delay and experimental comparison

DOI10.1016/j.dam.2020.04.036zbMath1478.05075OpenAlexW3035935184MaRDI QIDQ5918096

Christian Komusiewicz, Frank Sommer

Publication date: 15 September 2021

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

Full work available at URL: https://doi.org/10.1016/j.dam.2020.04.036

zbMATH Keywords

subgraph enumerationpolynomial delayenumeration algorithmreverse searchdegree-bounded graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality ⋮ Maximizing the influence with \(\kappa\)-grouping constraint

Uses Software

• KONECT
• FANMOD
• Kavosh
• Fixcon

Cites Work

• Unnamed Item
• Reverse search for enumeration
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Constant Time Enumeration by Amortization
• Finding Dense Subgraphs of Sparse Graphs
• FixCon: A Generic Solver for Fixed-Cardinality Subgraph Problems
• A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality

This page was built for publication: Enumerating connected induced subgraphs: improved delay and experimental comparison