The Maximum Solution Problem on Graphs

DOI10.1007/978-3-540-74456-6_22zbMath1147.68532OpenAlexW2099629445MaRDI QIDQ3525572

Johan Thapper, Gustav Nordh, Peter Jonsson

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 complexityhomomorphismsoptimisationconstraint satisfaction

Mathematics Subject Classification ID

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

Related Items

Necessary Conditions for Tractability of Valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ New plain-exponential time classes for graph homomorphism ⋮ Approximability of clausal constraints ⋮ Approximability of the Maximum Solution Problem for Certain Families of Algebras ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Introduction to the Maximum Solution Problem