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 (only showing first 100 items - show all)

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

Cites Work

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