Independent sets in asteroidal triple-free graphs
DOI10.1007/3-540-63165-8_229zbMATH Open1401.05278OpenAlexW2096691710MaRDI QIDQ4572004FDOQ4572004
Dieter Kratsch, Haiko Müller, Hajo Broersma, Ton Kloks
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Modular decomposition and transitive orientation
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Title not available (Why is that?)
- Complexity of Finding Embeddings in a k-Tree
- Representation of a finite graph by a set of intervals on the real line
- Treewidth. Computations and approximations
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
- The leafage of a chordal graph
- Domination and total domination on asteroidal triple-free graphs
- Computing the Minimum Fill-In is NP-Complete
- Vertex ranking of asteroidal triple-free graphs
- The NP-completeness column: an ongoing guide
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Triangulating graphs without asteroidal triples
- Weighted domination on cocomparability graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
Cited In (12)
- Asteroidal triples of moplexes
- On asteroidal sets in chordal graphs
- Title not available (Why is that?)
- Small \(k\)-pyramids and the complexity of determining \(k\)
- Title not available (Why is that?)
- Independent sets in graphs
- 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
- Title not available (Why is that?)
- On the algorithmic complexity of twelve covering and independence parameters of 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)
