Vertex packings: Structural properties and algorithms
From MaRDI portal
Cites work
- 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
- 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?)
- 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)- Single machine precedence constrained scheduling is a Vertex cover problem
- Approximation algorithms for the weighted independent set problem in sparse graphs
- On parameterized exponential time complexity
- On problems without polynomial kernels
- Efficient bounds for the stable set, vertex cover and set packing problems
- Random near-regular graphs and the node packing problem
- Equivalent approximation algorithms for node cover
- An algorithm to generate the ideals of a partial order
- An exact threshold theorem for random graphs and the node-packing problem
- Maximum weight independent set in trees
- Maximal chordal subgraphs
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Polytope des independants d'un graphe série-parallèle
- Discrete extremal problems
- Computing independent sets in graphs with large girth
- A new fixed point approach for stable networks and stable marriages
- A class of facet producing graphs for vertex packing polyhedra
- A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
- A fast algorithm for the maximum weight clique problem
- Network flow and 2-satisfiability
- The maximum clique problem
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- A rounding algorithm for integer programs
- A graph approximation heuristic for the vertex cover problem on planar graphs
- A multi-KP modeling for the maximum-clique problem
- Vertex packing problem application to the design of electronic testing fixtures
- Binary integer programs with two variables per inequality
- Improved approximations for maximum independent set via approximation chains
- A combinatorial column generation algorithm for the maximum stable set problem
- Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
- On approximability of linear ordering and related NP-optimization problems on graphs.
- Recent results on approximating the Steiner tree problem and its generalizations
- Erratum to ``Comparison of column generation models for channel assignment in cellular networks
- A (3+)k-vertex kernel for edge-disjoint triangle packing
- A 2k-kernelization algorithm for vertex cover based on crown decomposition
- A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
- Ramsey theory and integrality gap for the independent set problem
- Approximation for vertex cover in -conflict graphs
- On upper bounds for the independent transversal domination number
- The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
- The generalized vertex cover problem and some variations
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Approximating the dense set-cover problem
- Parameterized (in)approximability of subset problems
- Extended formulations for vertex cover
- König-Egerváry graphs, 2-bicritical graphs and fractional matchings
- A new greedoid: The family of local maximum stable sets of a forest
- On weighted vs unweighted versions of combinatorial optimization problems
- On the existence of subexponential parameterized algorithms
- Graph separators: A parameterized view
- Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
- Parametric formulation of the general integer linear programming problem
- Critical independent sets and König-Egerváry graphs
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- A kernel of order 2k-c k for vertex cover
- Fixed-parameter evolutionary algorithms and the vertex cover problem
- Pseudo-Hamiltonian-connected graphs
- Relaxing the strong triadic closure problem for edge strength inference
- The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP
- Polyhedral properties of the induced cluster subgraphs
- On a relation between \(k\)-path partition and \(k\)-path vertex cover
- The general graph matching game: approximate core
- Worst-case analysis of clique MIPs
- Dynamic node packing
- Persistency of linear programming relaxations for the stable set problem
- On the complexity of minimum \(q\)-domination partization problems
- Critical sets, crowns and local maximum independent sets
- New results relating independence and matchings
- Reoptimization of parameterized problems
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- The optimal statistical median of a convex set of arrays
- Kernels for packing and covering problems
- A branch-and-price approach for the partition coloring problem
- Integrality gap of the vertex cover linear programming relaxation
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Tractability of König edge deletion problems
- A completeness theory for polynomial (Turing) kernelization
- A linear-time kernelization for the rooted k-leaf outbranching problem
- Linear kernels for separating a graph into components of bounded size
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Additive stabilizers for unstable graphs
- Vertex cover in conflict graphs
- Using critical sets to solve the maximum independent set problem
- Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
- Crown reductions for the minimum weighted vertex cover problem
- A polyhedral study of the generalized vertex packing problem
- Experimental analysis of approximation algorithms for the vertex cover and set covering problems
- Berge's theorem for the maximum charge problem
- Tight lower bounds for certain parameterized NP-hard problems
- A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- A review on algorithms for maximum clique problems
- On unicyclic graphs with uniquely restricted maximum matchings
- Genus characterizes the complexity of certain graph problems: Some tight results
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Complementation in T-perfect graphs
- \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
- Vertex cover meets scheduling
- Kernelization of the 3-path vertex cover problem
- Half-integrality, LP-branching, and FPT algorithms
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)
