Implications of forbidden structures for extremal algorithmic problems

DOI10.1016/0304-3975(85)90166-5zbMath0603.68041OpenAlexW2009804249MaRDI QIDQ1082812

Ming-Deh A. Huang, Karl J. Lieberherr

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90166-5

zbMATH Keywords

combinatorial optimizationlinear time algorithmslogical relationsRAMforbidden subformulasgeneralized satisfiability problemsP- optimal approximation algorithmsP- optimal thresholds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Discrete mathematics in relation to computer science (68R99)

Related Items (5)

A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Partial Satisfaction of k-Satisfiable Formulas ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Locally consistent constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• Some simplified NP-complete graph problems
• Complexity of Partial Satisfaction
• Node-Deletion Problems on Bipartite Graphs
• Algorithmic extremal problems in combinatorial optimization
• P-Complete Approximation Problems
• The complexity of satisfiability problems
• On coloring graphs to maximize the proportion of multicolored k-edges

This page was built for publication: Implications of forbidden structures for extremal algorithmic problems