Complement, Complexity, and Symmetric Representation

DOI10.1142/S0129054115500318zbMath1330.68119OpenAlexW2220626745MaRDI QIDQ2949722

Thomas E. O'Neil

Publication date: 2 October 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054115500318

zbMATH Keywords

partitionindependent setcliqueNP-completepower indexvertex coversymmetric representationsub-exponential time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Cites Work

• Unnamed Item
• Exact and approximate bandwidth
• Which problems have strongly exponential complexity?
• An exact algorithm for MAX-CUT in sparse graphs
• Open problems around exact algorithms
• Algorithms for maximum independent sets
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• Computing Partitions with Applications to the Knapsack Problem
• 3-coloring in time
• Power indices and easier hard problems