On the parameterized complexity of non-hereditary relaxations of clique
DOI10.1016/J.TCS.2024.114625zbMATH Open1541.6827MaRDI QIDQ6549685FDOQ6549685
Authors: Ambroise Baril, Antoine Castillon, Nacim Oijid Edit this on Wikidata
Publication date: 4 June 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Fundamentals of parameterized complexity
- Reducibility among combinatorial problems
- The node-deletion problem for hereditary properties is NP-complete
- Classifying molecular sequences using a linkage graph with their pairwise similarities
- On the maximum quasi-clique problem
- Novel approaches for analyzing biological networks
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Improved upper bounds for vertex cover
- Finding maximum subgraphs with relatively large vertex connectivity
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- Isolation concepts for efficiently enumerating dense subgraphs
- Parameterized computational complexity of finding small-diameter subgraphs
- Parameterized complexity of finding subgraphs with hereditary properties.
- Listing all maximal cliques in sparse graphs in near-optimal time
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Multivariate algorithmics for finding cohesive subnetworks
- Hardness and tractability of the \(\gamma\)-complete subgraph problem
This page was built for publication: On the parameterized complexity of non-hereditary relaxations of clique
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6549685)
