Minimum node covers and 2-bicritical graphs

DOI10.1007/BF01588228zbMath0414.90066MaRDI QIDQ3050138

William R. Pulleyblank

Publication date: 1979

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

zbMATH Keywords

integer programmingmatchingstable setrandom graphbicritical graphsheuristic approachlinear relaxationnode coveringnode packingminimum cardinality set of nodesregularizable graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (21)

Determining the number of internal stability of a graph ⋮ Spectral radius and fractional matchings in graphs ⋮ Persistency of Linear Programming Relaxations for the Stable Set Problem ⋮ An exact threshold theorem for random graphs and the node-packing problem ⋮ New results relating independence and matchings ⋮ The difference and ratio of the fractional matching number and the matching number of graphs ⋮ Pseudo-Hamiltonian-connected graphs ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ The core of a graph ⋮ Berge's theorem for the maximum charge problem ⋮ Regularisable graphs, II ⋮ König-Egerváry graphs, 2-bicritical graphs and fractional matchings ⋮ Capacities of graphs and \(2\)-matchings ⋮ Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem ⋮ Sharp lower bounds on the fractional matching number ⋮ Random near-regular graphs and the node packing problem ⋮ A decomposition algorithm for linear relaxation of the weightedr-covering problem ⋮ The maximum clique problem ⋮ 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On colouring random graphs
• Vertex packings: Structural properties and algorithms
• On the integer-valued variables in the linear vertex packing problem
• Determining the Stability Number of a Graph
• Determining the Chromatic Number of a Graph
• Integer Programming: Methods, Uses, Computations
• Maximum matching and a polyhedron with 0,1-vertices
• Some remarks on the theory of graphs
• The Factors of Graphs

This page was built for publication: Minimum node covers and 2-bicritical graphs