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

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

Cited In (only showing first 100 items - show all)

Solving min ones 2-SAT as fast as vertex cover
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
Approximation algorithms for the weighted independent set problem in sparse graphs
Kernelization: new upper and lower bound techniques
A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
Roof duality, complementation and persistency in quadratic 0–1 optimization
König-Egerváry graphs, 2-bicritical graphs and fractional matchings
Minimum vertex cover in rectangle graphs
The maximum clique problem
Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
Generalized roof duality and bisubmodular functions
Vertex cover meets scheduling
Crown reductions for the minimum weighted vertex cover problem
A randomized polynomial kernelization for vertex cover with a smaller parameter
Quadratic kernelization for convex recoloring of trees
Parametric formulation of the general integer linear programming problem
Efficient bounds for the stable set, vertex cover and set packing problems
A generalization of Nemhauser and Trotter's local optimization theorem
A kernel of order \(2k-c\log k\) for vertex cover
Smaller parameters for vertex cover kernelization
An algorithm to generate the ideals of a partial order
Randomized approximation of bounded multicovering problems
Tight lower bounds for certain parameterized NP-hard problems
Pseudo-Boolean optimization
A basic parameterized complexity primer
A kernelization algorithm for \(d\)-hitting set
Kernelization of the 3-path vertex cover problem
On problems without polynomial kernels
Improved upper bounds for vertex cover
Recent results on approximating the Steiner tree problem and its generalizations
Combinatorics for smaller kernels: the differential of a graph
On miniaturized problems in parameterized complexity theory
A class of facet producing graphs for vertex packing polyhedra
Compression via matroids: a randomized polynomial kernel for odd cycle transversal
Distributionally robust mixed integer linear programs: persistency models with applications
Computing independent sets in graphs with large girth
Title not available (Why is that?)
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
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
The Clique Corona Operation and Greedoids
The Boolean quadratic polytope: Some characteristics, facets and relatives
Ramsey numbers and an approximation algorithm for the vertex cover problem
Approximability of the vertex cover problem in power-law graphs
Complexity of most vital nodes for independent set in graphs related to tree structures
How tight is the corner relaxation? Insights gained from the stable set problem
On local maximum stable set greedoids
A branch and cut solver for the maximum stable set problem
Network flow and 2-satisfiability
Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
The Hirsch conjecture for the fractional stable set polytope
Graph operations that are good for greedoids
Maximal chordal subgraphs
Strong computational lower bounds via parameterized complexity
Polytope des independants d'un graphe série-parallèle
A branch-and-price approach for the partition coloring problem
A cubic kernel for feedback vertex set and loop cutset
Local maximum stable set greedoids stemming from very well-covered graphs
Random near-regular graphs and the node packing problem
An exact threshold theorem for random graphs and the node-packing problem
A fast algorithm for the maximum weight clique problem
Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
On the existence of subexponential parameterized algorithms
Fixed interval scheduling: models, applications, computational complexity and algorithms
Half-integrality, LP-branching, and FPT algorithms
A new greedoid: The family of local maximum stable sets of a forest
Approximating the dense set-cover problem
Critical independent sets and König-Egerváry graphs
Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
Minimum node covers and 2-bicritical graphs
Parameterized (in)approximability of subset problems
A Problem Kernelization for Graph Packing
Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
Very well-covered graphs of girth at least four and local maximum stable set greedoids
Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering
Finding maximum cliques in arbitrary and in special graphs
Reoptimization of parameterized problems
A kernel of order \(2k - c\) for Vertex Cover
Kernels for packing and covering problems
A review on algorithms for maximum clique problems
The complexity ecology of parameters: An illustration using bounded max leaf number
On approximation properties of the Independent set problem for degree 3 graphs
Computing solutions for matching games
Some facets of the simple plant location polytope
On weighted vs unweighted versions of combinatorial optimization problems
Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
Vertex packing problem application to the design of electronic testing fixtures
Autarkies and Persistencies for QUBO
Single machine precedence constrained scheduling is a Vertex cover problem
On approximation problems related to the independent set and vertex cover problems
A completeness theory for polynomial (Turing) kernelization
Approximating edge dominating set in dense graphs
Vertex cover in graphs with locally few colors
Finding the maximal internally stable set of a graph
When polynomial approximation meets exact computation
On the integer-valued variables in the linear vertex packing problem
Ramsey theory and integrality gap for the independent set problem

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)