Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
From MaRDI portal
Publication:1401202
DOI10.1016/S0304-3975(02)00329-8zbMath1044.68163MaRDI QIDQ1401202
Antonio Puricella, Iain A. Stewart
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00329-8
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of H-coloring
- On generating all maximal independent sets
- List homomorphisms to reflexive graphs
- \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
- List homomorphisms and circular arc graphs
- Complete Problems Involving Boolean Labelled Structures and Projection Transactions
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms