Independent sets in asteroidal triple-free graphs

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

Mathematics Subject Classification ID

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