The Maximum Solution Problem on Graphs

DOI10.1007/978-3-540-74456-6_22MaRDI QIDQ3525572zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Gustav Nordh, Johan Thapper

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_22

zbMATH Keywords

computational complexityoptimisationconstraint satisfactionhomomorphisms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Introduction to the Maximum Solution Problem
• Extensions of the minimum cost homomorphism problem
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• Minimum cost homomorphisms with constrained costs
• scientific article; zbMATH DE number 2151253

Cited in

(12)

• Approximability of clausal constraints
• Introduction to the Maximum Solution Problem
• New Plain-Exponential Time Classes for Graph Homomorphism
• Optimal maximal graphs
• The Max-Atom Problem and Its Relevance
• The power of Sherali-Adams relaxations for general-valued CSPs
• The Maximum Labeled Path Problem
• Necessary conditions for tractability of valued CSPs
• Morphisms for the maximum weight ideal problem
• New plain-exponential time classes for graph homomorphism
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• The density maximization problem in graphs

This page was built for publication: The Maximum Solution Problem on Graphs

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