On the max min vertex cover problem
DOI10.1016/J.DAM.2014.06.001zbMATH Open1321.05177OpenAlexW1968988491MaRDI QIDQ499339FDOQ499339
Authors: Nicolas Boria, Vangelis Th. Paschos, F. Della Croce 
Publication date: 30 September 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.06.001
Recommendations
- On the max min vertex cover problem
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- scientific article; zbMATH DE number 2080196
- On approximability of the independent/connected edge dominating set problems
- Maximum minimal vertex cover parameterized by vertex cover
inapproximabilitypolynomial approximationmax min vertex covermin independent dominating setparametric complexity
Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Parameterized Approximation Problems
- Approximating the minimum maximal independence number
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Domination, independent domination, and duality in strongly chordal graphs
- Title not available (Why is that?)
- Parameterized approximation via fidelity preserving transformations
- Fast algorithms for min independent dominating set
- The approximation of maximum subgraph problems
- New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
- On Parameterized Approximability
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- On Turan's theorem for sparse graphs
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
- Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
- Title not available (Why is that?)
- Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
Cited In (25)
- A maximum dicut in a digraph induced by a minimal dominating set
- Computing the largest bond and the maximum connected cut of a graph
- Matroid-constrained vertex cover
- Extension and its price for the connected vertex cover problem
- The Probabilistic Minimum Vertex-covering Problem
- In)approximability of Maximum Minimal FVS
- On the complexity of minimum maximal acyclic matchings
- Algorithms - ESA 2003
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- \textsc{MAX MIN} vertex cover and the size of Betti tables
- Weighted upper edge cover: complexity and approximability
- Maximum minimal vertex cover parameterized by vertex cover
- Minimum maximal acyclic matching in proper interval graphs
- On the max min vertex cover problem
- (In)approximability of maximum minimal FVS
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Minimal zero forcing sets
- An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
- Upper Clique Transversals in Graphs
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Complexity of the max cut problem with the minimal domination constraint
- Maximum minimal vertex cover parameterized by vertex cover
- On the complexity of minimum maximal acyclic matchings
- Minimum maximal acyclic matching in proper interval graphs
This page was built for publication: On the max min vertex cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499339)
