Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
From MaRDI portal
Publication:1627852
DOI10.1016/j.dam.2018.05.032zbMath1401.05070OpenAlexW2808514443WikidataQ115577869 ScholiaQ115577869MaRDI QIDQ1627852
Yi-Zhi Liu, Li-Hsuan Chen, Maw-Shang Chang, Somnath Sikdar, Peter Rossmanith, Ling-Ju Hung
Publication date: 3 December 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.032
Cites Work
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Combinatorial algorithms for the maximum \(k\)-plex problem
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- Exact exponential algorithms.
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- A generalization of Nemhauser and Trotter's local optimization theorem
- On bounded-degree vertex deletion parameterized by treewidth
- On the hardness of approximating minimum vertex cover
- Isolation concepts for efficiently enumerating dense subgraphs
- An improved kernelization for \(P_{2}\)-packing
- A new approach for approximating node deletion problems
- A unified approximation algorithm for node-deletion problems
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- Exact algorithms for maximum independent set
- Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- A Linear Kernel for Co-Path/Cycle Packing
- A graph‐theoretic generalization of the clique concept
- Approximating Bounded Degree Deletion via Matroid Matching
