Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
From MaRDI portal
Publication:6145807
DOI10.1016/j.dam.2023.10.025zbMath1530.05087arXiv2007.01031OpenAlexW4323714698MaRDI QIDQ6145807
Lucas Pastor, Arnaud Mary, Aurélie Lagoutte, Vincent Limouzy, Caroline Brosse
Publication date: 9 January 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.01031
Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Minimal split completions
- Characterizing and computing minimal cograph completions
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- On generating all maximal independent sets
- The node-deletion problem for hereditary properties is NP-complete
- Complement reducible graphs
- Efficient enumeration of bipartite subgraphs in graphs
- Algorithmic graph theory and perfect graphs
- Reverse search for enumeration
- On the complexity of solution extension of optimization problems
- Enumeration of maximal common subsequences between two strings
- Analysis and enumeration. Algorithms for biological graphs
- On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
- On Maximal Chain Subgraphs and Covers of Bipartite Graphs
- A Linear Recognition Algorithm for Cographs
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Edge-Deletion Problems
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- A New Algorithm for Generating All the Maximal Independent Sets
- Finding All Spanning Trees of Directed and Undirected Graphs
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- Graph Sandwich Problems
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- New polynomial delay bounds for maximal subgraph enumeration by proximity search
- On the Enumeration of Minimal Dominating Sets and Related Notions
- Faster and enhanced inclusion-minimal cograph completion
- On cliques in graphs
