A Lower Bound for Treewidth and Its Consequences.
Siddharthan RamachandramurthiPublished in: WG (1994)
Keyphrases
- upper bound
- lower bound
- worst case
- branch and bound algorithm
- branch and bound
- optimal solution
- bounded treewidth
- upper and lower bounds
- lower and upper bounds
- np hard
- vc dimension
- negative consequences
- space complexity
- lower bounding
- search space
- objective function
- sample complexity
- boolean functions
- linear programming relaxation
- competitive ratio
- branch and bound method
- lagrangian relaxation
- constant factor