A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles

DOI10.1007/BF01589347zbMath0452.90084OpenAlexW2068244470MaRDI QIDQ3899836

No author found.

Publication date: 1981

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

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

zbMATH Keywords

combinatorial optimizationgraph theorypolynomial algorithmvertex packing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Determining the number of internal stability of a graph, An exact algorithm for the maximum stable set problem, An algorithm for the maximum internally stable set in a weighted graph, On the vertex packing problem, New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths, On the use of Boolean methods for the computation of the stability number, Strongly polynomial simplex algorithm for bipartite vertex packing, An algorithm for finding a maximum weighted independent set in an arbitrary graph, Polyhedral characterizations and perfection of line graphs, The list chromatic index of simple graphs whose odd cycles intersect in at most one edge, Unnamed Item, A polynomial algorithm for the max-cut problem on graphs without long odd cycles, A branch and bound algorithm for the maximum clique problem, Stability number of bull- and chair-free graphs, Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering, Polynomial kernels for vertex cover parameterized by small degree modulators, Enumerating all connected maximal common subgraphs in two graphs, Finding maximum cliques in arbitrary and in special graphs, Tuza's conjecture for graphs with maximum average degree less than 7, The maximum clique problem

Cites Work

• On maximal independent sets of vertices in claw-free graphs
• Some simplified NP-complete graph problems
• Anti-blocking polyhedra
• Line perfect graphs
• Properties of vertex packing and independence system polyhedra
• Paths, Trees, and Flowers
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item