On the parameterized complexity of non-hereditary relaxations of clique
From MaRDI portal
Publication:6549685
DOI10.1016/J.TCS.2024.114625zbMATH Open1541.6827MaRDI QIDQ6549685FDOQ6549685
Antoine Castillon, Ambroise Baril, Nacim Oijid
Publication date: 4 June 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
- On structural parameterizations for the 2-club problem
- 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\)\textsf{-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)
