Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem

DOI10.1016/j.ipl.2021.106105OpenAlexW3128433249MaRDI QIDQ2032141

Ambroise Baril, Riccardo Dondi, Mohammad Mehdi Hosseinzadeh

Publication date: 16 June 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106105

zbMATH Keywords

graph algorithmsparameterized complexityclique relaxations\(\gamma\)-complete graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Isolation concepts for efficiently enumerating dense subgraphs
• Classifying molecular sequences using a linkage graph with their pairwise similarities
• Multivariate algorithmics for finding cohesive subnetworks
• Parameterized computational complexity of finding small-diameter subgraphs
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• Novel approaches for analyzing biological networks
• Finding disjoint dense clubs in a social network
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• A graph‐theoretic definition of a sociometric clique†
• Color-coding
• On maximum degree‐based ‐quasi‐clique problem: Complexity and exact approaches
• The Parameterized Complexity of the k -Biclique Problem
• Reducibility among Combinatorial Problems
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Covering a Graph with Clubs
• Parameterized Algorithms

This page was built for publication: Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem