Implications of forbidden structures for extremal algorithmic problems
type: Item
instance of: scholarly article
title: Implications of forbidden structures for extremal algorithmic problems
zbMATH Open document ID: 0603.68041
DOI: 10.1016/0304-3975(85)90166-5
author: Ming-Deh A. Huang
author: Karl J. Lieberherr
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: We develop and analyze P-optimal approximation algorithms for various generalized satisfiability problems and determine the corresponding P- optimal thresholds. The most novel aspect of the paper is that we develop new P-optimal algorithms for restricted generalized satisfiability problems which are defined by forbidden subformulas. All our algorithms run in linear time on a RAM.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68R99
zbMATH DE Number: 3974290
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: linear time algorithms
zbMATH Keywords: logical relations
zbMATH Keywords: P- optimal approximation algorithms
zbMATH Keywords: generalized satisfiability problems
zbMATH Keywords: P- optimal thresholds
zbMATH Keywords: forbidden subformulas
zbMATH Keywords: RAM
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90166-5
OpenAlex ID: W2009804249
cites work: Q5588434
cites work: On coloring graphs to maximize the proportion of multicolored k-edges
cites work: Q3905312
cites work: Some simplified NP-complete graph problems
cites work: Q4198056
cites work: Approximation algorithms for combinatorial problems
cites work: Complexity of Partial Satisfaction
cites work: Algorithmic extremal problems in combinatorial optimization
cites work: Node-Deletion Problems on Bipartite Graphs
cites work: P-Complete Approximation Problems
cites work: The complexity of satisfiability problems
Recommended article: Q3347927
Recommended article: Forbidden lifts (NP and CSP for combinatorialists)
Recommended article: Complexity of the path avoiding forbidden pairs problem revisited
Recommended article: The Tractability of CSP Classes Defined by Forbidden Patterns
Recommended article: NEWLY FOUND FORBIDDEN GRAPHS FOR TRIVIALIZABILITY
Recommended article: Generalized forbidden subposet problems
Recommended article: On the complexity of paths avoiding forbidden pairs
Recommended article: Q4770385
description: scientific article; zbMATH DE number 3974290