Independent sets in asteroidal triple-free graphs

DOI10.1007/3-540-63165-8_229MaRDI QIDQ4572004zbMATH OpenOpenAlexFDO

Authors Ton Kloks, Dieter Kratsch, Haiko Müller, Hajo 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

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Independent Sets in Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• A linear time algorithm to compute a dominating path in an AT-free graph
• Domination and total domination on asteroidal triple-free graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Domination and total domination on asteroidal triple-free graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Modular decomposition and transitive orientation
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• The NP-completeness column: an ongoing guide
• The leafage of a chordal graph
• Treewidth. Computations and approximations
• Triangulating graphs without asteroidal triples
• Vertex ranking of asteroidal triple-free graphs
• Weighted domination on cocomparability graphs

Cited in

(14)

• Asteroidal triples of moplexes
• On asteroidal sets in chordal graphs
• scientific article; zbMATH DE number 1420922 (Why is no real title available?)
• Small \(k\)-pyramids and the complexity of determining \(k\)
• Independent sets in graphs
• Recognizing graphs without asteroidal triples
• scientific article; zbMATH DE number 1420489 (Why is no real title available?)
• Induced matchings in asteroidal triple-free graphs
• A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
• Domination and total domination on asteroidal triple-free graphs
• scientific article; zbMATH DE number 1696539 (Why is no real title available?)
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Colouring AT-free graphs
• Connected domination and steiner set on asteroidal triple-free graphs

This page was built for publication: Independent sets in asteroidal triple-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4572004)