A polynomial characterization of some graph partitioning problems

DOI10.1016/0020-0190(88)90144-5zbMath0654.68093OpenAlexW2044936198MaRDI QIDQ1108810

Claudio Arbib

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90144-5

zbMATH Keywords

polynomial algorithmgraph partitioningline-graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, The equipartition polytope. I: Formulations, dimension and basic facets, Some new classes of facets for the equicut polytope, Unnamed Item, \textsc{max-cut} and containment relations in graphs, Representations of graphs and networks (coding, layouts and embeddings), max-cut and Containment Relations in Graphs, Maximum cut on line and total graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Some simplified NP-complete graph problems
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• An Efficient Heuristic Procedure for Partitioning Graphs
• On the cut polytope