Independent sets in asteroidal triple-free graphs
From MaRDI portal
Publication:4572004
DOI10.1007/3-540-63165-8_229zbMath1401.05278MaRDI QIDQ4572004
Dieter Kratsch, Haiko Müller, Ton Kloks, Hajo J. Broersma
Publication date: 4 July 2018
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-63165-8_229
68W40: Analysis of algorithms
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Unnamed Item, Independent sets in graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, Domination and total domination on asteroidal triple-free graphs, Small \(k\)-pyramids and the complexity of determining \(k\)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Modular decomposition and transitive orientation
- Treewidth. Computations and approximations
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Triangulating graphs without asteroidal triples
- Domination and total domination on asteroidal triple-free graphs
- Representation of a finite graph by a set of intervals on the real line
- The NP-completeness column: an ongoing guide
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- The leafage of a chordal graph
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
