Vertex packings: Structural properties and algorithms

DOI10.1007/BF01580444zbMath0314.90059OpenAlexW2013415302WikidataQ56814665 ScholiaQ56814665MaRDI QIDQ4074668

Nemhauser, George I., Leslie E. jun. Trotter

Publication date: 1975

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580444

Mathematics Subject Classification ID

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

Related Items

A rounding algorithm for integer programs, On miniaturized problems in parameterized complexity theory, Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Equivalent approximation algorithms for node cover, Vertex cover meets scheduling, A graph approximation heuristic for the vertex cover problem on planar graphs, A multi-KP modeling for the maximum-clique problem, On the existence of subexponential parameterized algorithms, Compactors for parameterized counting problems, Kernelization of the 3-path vertex cover problem, An algorithm to generate the ideals of a partial order, An edge-reduction algorithm for the vertex cover problem, Vertex packing problem application to the design of electronic testing fixtures, A $(3+\epsilon)k$-vertex kernel for edge-disjoint triangle packing, Distributionally robust mixed integer linear programs: persistency models with applications, An exact threshold theorem for random graphs and the node-packing problem, A $2k$-kernelization algorithm for vertex cover based on crown decomposition, Maximum weight independent set in trees, Strong computational lower bounds via parameterized complexity, A comparative study of formulations and solution methods for the discrete ordered $p$-median problem, On a generalization of Nemhauser and Trotter's local optimization theorem, Binary integer programs with two variables per inequality, Fixed interval scheduling: models, applications, computational complexity and algorithms, Maximal chordal subgraphs, Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover, Improved approximations for maximum independent set via approximation chains, A combinatorial column generation algorithm for the maximum stable set problem, Ramsey theory and integrality gap for the independent set problem, The Boolean quadratic polytope: Some characteristics, facets and relatives, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Approximability of the vertex cover problem in power-law graphs, Approximation for vertex cover in $\beta$-conflict graphs, 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, Generalized roof duality and bisubmodular functions, On upper bounds for the independent transversal domination number, Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover, Polytope des independants d'un graphe série-parallèle, Discrete extremal problems, Quadratic kernelization for convex recoloring of trees, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Local maximum stable set greedoids stemming from very well-covered graphs, How tight is the corner relaxation? Insights gained from the stable set problem, The Hirsch conjecture for the fractional stable set polytope, On approximability of linear ordering and related NP-optimization problems on graphs., Confronting intractability via parameters, A generalization of Nemhauser and Trotter's local optimization theorem, On local maximum stable set greedoids, Combinatorics for smaller kernels: the differential of a graph, Computing solutions for matching games, Computing independent sets in graphs with large girth, A branch and cut solver for the maximum stable set problem, Iterative improvement of vertex covers, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, Randomized approximation of bounded multicovering problems, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Crowns in bipartite graphs, The relationship between attribute reducts in rough sets and minimal vertex covers of graphs, A new fixed point approach for stable networks and stable marriages, The generalized vertex cover problem and some variations, A kernel of order $2k - c$ for Vertex Cover, Hooked on IP, Pseudo-Boolean optimization, A cubic kernel for feedback vertex set and loop cutset, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Approximating the dense set-cover problem, Minimum vertex cover in rectangle graphs, A class of facet producing graphs for vertex packing polyhedra, Improved upper bounds for vertex cover, On approximating minimum vertex cover for graphs with perfect matching, Graph operations that are good for greedoids, A note on the greedy algorithm for finding independent sets of $C_k$-free graphs, A kernelization algorithm for $d$-hitting set, Linear kernelizations for restricted 3-Hitting Set problems, Parameterized (in)approximability of subset problems, Approximability of clique transversal in perfect graphs, Extended formulations for vertex cover, The complexity ecology of parameters: An illustration using bounded max leaf number, Single machine precedence constrained scheduling is a Vertex cover problem, On approximation problems related to the independent set and vertex cover problems, Approximation algorithms for the weighted independent set problem in sparse graphs, Ramsey numbers and an approximation algorithm for the vertex cover problem, On parameterized exponential time complexity, A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios, Approximating edge dominating set in dense graphs, Recent results on approximating the Steiner tree problem and its generalizations, Strong and weak edges of a graph and linkages with the vertex cover problem, König-Egerváry graphs, 2-bicritical graphs and fractional matchings, On problems without polynomial kernels, A new greedoid: The family of local maximum stable sets of a forest, Efficient bounds for the stable set, vertex cover and set packing problems, On certain classes of fractional matchings, On weighted vs unweighted versions of combinatorial optimization problems, Random near-regular graphs and the node packing problem, Erratum to ``Comparison of column generation models for channel assignment in cellular networks, Finding maximum cliques in arbitrary and in special graphs, 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, Kernelization for feedback vertex set via elimination distance to a forest, Kernelization for feedback vertex set via elimination distance to a forest, Approximate core allocations for edge cover games, A theoretical and computational analysis of full strong-branching, A polytime preprocess algorithm for the maximum independent set problem, Neighborhood persistency of the linear optimization relaxation of integer linear optimization, Space limited linear-time graph algorithms on big data, When polynomial approximation meets exact computation, Exploiting c-Closure in Kernelization Algorithms for Graph Problems, When polynomial approximation meets exact computation, A branch and bound algorithm for the maximum clique problem, A quadratic programming approach to the determination of an upper bound on the weighted stability number, Comparison of column generation models for channel assignment in cellular networks, Finding all $k$-cliques in $k$-partite graphs, an application in textile engineering, Parameterized certificate dispersal and its variants, Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems, The Clique Corona Operation and Greedoids, Unnamed Item, Unnamed Item, Determining the number of internal stability of a graph, Linear kernels for separating a graph into components of bounded size, On the complexity of minimum $q$-domination partization problems, Graph separators: A parameterized view, Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms, Finding the maximal internally stable set of a graph, Persistency of Linear Programming Relaxations for the Stable Set Problem, Safe Approximation and Its Relation to Kernelization, Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds, Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, Autarkies and Persistencies for QUBO, A review on algorithms for maximum clique problems, A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter, On approximation properties of the Independent set problem for degree 3 graphs, A Basic Parameterized Complexity Primer, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, What’s Next? Future Directions in Parameterized Complexity, Primal-dual approximation algorithms for feedback problems in planar graphs, On unicyclic graphs with uniquely restricted maximum matchings, Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms, Critical sets, crowns and local maximum independent sets, New results relating independence and matchings, Genus characterizes the complexity of certain graph problems: Some tight results, Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation, Finding near-optimal independent sets at scale, Reoptimization of parameterized problems, Estimating the Size of Branch-and-Bound Trees, Parametric formulation of the general integer linear programming problem, Sparsification upper and lower bounds for graph problems and not-all-equal SAT, Critical independent sets and König-Egerváry graphs, Exact combinatorial algorithms and experiments for finding maximum $k$-plexes, Preprocessing to reduce the search space: antler structures for feedback vertex set, Complementation in T-perfect graphs, Approximation and Kernelization for Chordal Vertex Deletion, Elimination Distances, Blocking Sets, and Kernels for Vertex Cover, Data Reduction for Maximum Matching on Real-World Graphs, Additive stabilizers for unstable graphs, $p$-edge/vertex-connected vertex cover: parameterized and approximation algorithms, On the 2-Club Polytope of Graphs, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Vertex cover in conflict graphs, Unnamed Item, A kernel of order $2k-c\log k$ for vertex cover, Polynomial kernels for hitting forbidden minors under structural parameterizations, Fixed-parameter evolutionary algorithms and the vertex cover problem, Technical Note—Assortment Optimization with Small Consideration Sets, Pseudo-Hamiltonian-connected graphs, Unnamed Item, Using critical sets to solve the maximum independent set problem, Why Is Maximum Clique Often Easy in Practice?, Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids, Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations., Approximating Edge Dominating Set in Dense Graphs, Relaxing the strong triadic closure problem for edge strength inference, Recoverable Values for Independent Sets, Vertex Cover in Graphs with Locally Few Colors, Crown reductions for the minimum weighted vertex cover problem, Unnamed Item, The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP, On the integer-valued variables in the linear vertex packing problem, A polyhedral study of the generalized vertex packing problem, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, The optimal statistical median of a convex set of arrays, Kernels for packing and covering problems, Minimum node covers and 2-bicritical graphs, Polyhedral properties of the induced cluster subgraphs, A Problem Kernelization for Graph Packing, A branch-and-price approach for the partition coloring problem, Berge's theorem for the maximum charge problem, On König-Egerváry collections of maximum critical independent sets, On a relation between $k$-path partition and $k$-path vertex cover, Integrality gap of the vertex cover linear programming relaxation, Half-integrality, LP-branching, and FPT Algorithms, On the Power of Simple Reductions for the Maximum Independent Set Problem, VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS, Stabilizing Weighted Graphs, Polynomial kernels for vertex cover parameterized by small degree modulators, On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph, Kernelization: New Upper and Lower Bound Techniques, The general graph matching game: approximate core, Smaller Parameters for Vertex Cover Kernelization, Tight lower bounds for certain parameterized NP-hard problems, Tractability of König edge deletion problems, Worst-case analysis of clique MIPs, Algorithm of determination of largest internally stable set of a graph, 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, Dynamic node packing, An extension of the edge covering problem, A completeness theory for polynomial (Turing) kernelization, Some facets of the simple plant location polytope, Unicycle graphs and uniquely restricted maximum matchings, Moderately exponential time and fixed parameter approximation algorithms, A decomposition algorithm for linear relaxation of the weightedr-covering problem, A linear-time kernelization for the rooted $k$-leaf outbranching problem, Roof duality, complementation and persistency in quadratic 0–1 optimization, Persistency of linear programming relaxations for the stable set problem, Vertices Belonging to All or to No Maximum Stable Sets of a Graph

Cites Work