A polynomial characterization of some graph partitioning problems

DOI10.1016/0020-0190(88)90144-5zbMATH Open0654.68093OpenAlexW2044936198MaRDI QIDQ1108810FDOQ1108810

Authors: 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

Recommendations

• scientific article; zbMATH DE number 4112413
• Generalized partitions of graphs
• The partition problem
• scientific article; zbMATH DE number 3970117
• Restrictions of graph partition problems. I

zbMATH Keywords

graph partitioningpolynomial algorithmline-graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• The equipartition polytope. I: Formulations, dimension and basic facets
• On uniform \(k\)-partition problems
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• Some new classes of facets for the equicut polytope
• \textsc{max-cut} and containment relations in graphs
• SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
• Max-Cut and containment relations in graphs
• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
• A solution to Gutman's problem on the characteristic polynomial of a bipartite graph
• Title not available (Why is that?)
• Maximum cut on line and total graphs
• Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps
• A P-complete graph partition problem
• Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: A polynomial characterization of some graph partitioning problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108810)