On the parameterized complexity of non-hereditary relaxations of clique
From MaRDI portal
Publication:6549685
DOI10.1016/j.tcs.2024.114625zbMATH Open1541.6827MaRDI QIDQ6549685
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
- Finding maximum subgraphs with relatively large vertex connectivity
- Fundamentals of parameterized complexity
- Improved upper bounds for vertex cover
- Isolation concepts for efficiently enumerating dense subgraphs
- The node-deletion problem for hereditary properties is NP-complete
- Classifying molecular sequences using a linkage graph with their pairwise similarities
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- Multivariate algorithmics for finding cohesive subnetworks
- Parameterized computational complexity of finding small-diameter subgraphs
- On the maximum quasi-clique problem
- Parameterized complexity of finding subgraphs with hereditary properties.
- Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem
- On structural parameterizations for the 2-club problem
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Novel approaches for analyzing biological networks
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
- Reducibility among Combinatorial Problems
This page was built for publication: On the parameterized complexity of non-hereditary relaxations of clique
