Vertex packings: Structural properties and algorithms

Programming involving graphs or networks (90C35) Integer programming (90C10) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Cites work

scientific article; zbMATH DE number 3159208 (Why is no real title available?)
scientific article; zbMATH DE number 3174052 (Why is no real title available?)
scientific article; zbMATH DE number 3361920 (Why is no real title available?)
Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
An Improved Implicit Enumeration Approach for Integer Programming
Anti-blocking polyhedra
Covers and packings in a family of sets
Edmonds polytopes and a hierarchy of combinatorial problems
On certain polytopes associated with graphs
On the facial structure of set packing polyhedra
Paths, Trees, and Flowers
Properties of vertex packing and independence system polyhedra
Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems

Cited in

(only showing first 100 items - show all)

Solving min ones 2-SAT as fast as vertex cover
On unicyclic graphs with uniquely restricted maximum matchings
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
A graph approximation heuristic for the vertex cover problem on planar graphs
Polynomial kernels for hitting forbidden minors under structural parameterizations
Compactors for parameterized counting problems
Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
Vertex cover in conflict graphs
A theoretical and computational analysis of full strong-branching
Approximation algorithms for the weighted independent set problem in sparse graphs
Dynamic node packing
A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
König-Egerváry graphs, 2-bicritical graphs and fractional matchings
Hooked on IP
Kernelization: new upper and lower bound techniques
Roof duality, complementation and persistency in quadratic 0–1 optimization
\(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
Minimum vertex cover in rectangle graphs
A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
Maximum weight independent set in trees
The maximum clique problem
Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
A new fixed point approach for stable networks and stable marriages
Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
A decomposition algorithm for linear relaxation of the weightedr-covering problem
Fixed-parameter evolutionary algorithms and the vertex cover problem
Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
Generalized roof duality and bisubmodular functions
Data Reduction for Maximum Matching on Real-World Graphs
Constructive -- non-constructive approximation and maximum independent set problem
Vertex cover meets scheduling
Sparsification upper and lower bounds for graph problems and not-all-equal SAT
An extension of the edge covering problem
Graph separators: A parameterized view
Crown reductions for the minimum weighted vertex cover problem
Quadratic kernelization for convex recoloring of trees
Efficient bounds for the stable set, vertex cover and set packing problems
A generalization of Nemhauser and Trotter's local optimization theorem
Unicycle graphs and uniquely restricted maximum matchings
A rounding algorithm for integer programs
Randomized approximation of bounded multicovering problems
Parametric formulation of the general integer linear programming problem
An algorithm to generate the ideals of a partial order
Pseudo-Boolean optimization
A randomized polynomial kernelization for vertex cover with a smaller parameter
A kernel of order \(2k-c\log k\) for vertex cover
Kernelization for feedback vertex set via elimination distance to a forest
What's next? Future directions in parameterized complexity
Tight lower bounds for certain parameterized NP-hard problems
Persistency of linear programming relaxations for the stable set problem
Estimating the Size of Branch-and-Bound Trees
Smaller parameters for vertex cover kernelization
A kernelization algorithm for \(d\)-hitting set
A polytime preprocess algorithm for the maximum independent set problem
Persistency of linear programming relaxations for the stable set problem
Kernelization of the 3-path vertex cover problem
A basic parameterized complexity primer
On König-Egerváry collections of maximum critical independent sets
Technical note: Assortment optimization with small consideration sets
A branch and bound algorithm for the maximum clique problem
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP
On problems without polynomial kernels
Improved upper bounds for vertex cover
A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
On the complexity of minimum \(q\)-domination partization problems
Determining the number of internal stability of a graph
Kernelization for feedback vertex set via elimination distance to a forest
Combinatorics for smaller kernels: the differential of a graph
Recent results on approximating the Steiner tree problem and its generalizations
A polyhedral study of the generalized vertex packing problem
On approximating minimum vertex cover for graphs with perfect matching
Approximation and kernelization for chordal vertex deletion
On miniaturized problems in parameterized complexity theory
A (3+)k-vertex kernel for edge-disjoint triangle packing
Experimental analysis of approximation algorithms for the vertex cover and set covering problems
A class of facet producing graphs for vertex packing polyhedra
Neighborhood persistency of the linear optimization relaxation of integer linear optimization
On approximability of linear ordering and related NP-optimization problems on graphs.
A quadratic programming approach to the determination of an upper bound on the weighted stability number
Primal-dual approximation algorithms for feedback problems in planar graphs
Linear kernelizations for restricted 3-Hitting Set problems
A linear-time kernelization for the rooted k-leaf outbranching problem
On duality between local maximum stable sets of a graph and its line-graph
Ultimate greedy approximation of independent sets in subcubic graphs
Approximability of clique transversal in perfect graphs
Compression via matroids: a randomized polynomial kernel for odd cycle transversal
Distributionally robust mixed integer linear programs: persistency models with applications
Polynomial kernels for vertex cover parameterized by small degree modulators
Relaxing the strong triadic closure problem for edge strength inference
Exploiting c-Closure in Kernelization Algorithms for Graph Problems
On the parallel parameterized complexity of MaxSAT variants
Computing independent sets in graphs with large girth
A combinatorial column generation algorithm for the maximum stable set problem
Algorithm of determination of largest internally stable set of a graph
Polyhedral properties of the induced cluster subgraphs
The generalized vertex cover problem and some variations
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
Erratum to ``Comparison of column generation models for channel assignment in cellular networks

This page was built for publication: Vertex packings: Structural properties and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4074668)