Independent sets in asteroidal triple-free graphs
From MaRDI portal
Publication:4572004
DOI10.1007/3-540-63165-8_229zbMath1401.05278OpenAlexW2096691710MaRDI 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
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
Unnamed Item ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ Independent sets in graphs ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs
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
This page was built for publication: Independent sets in asteroidal triple-free graphs