Publication:3694712
From MaRDI portal
zbMath0575.68069MaRDI QIDQ3694712
Andreas Brandstädt, Dieter Kratsch
Publication date: 1985
spanning tree; Hamiltonian circuit; crossing number; dominating set; polynomial time; Hamiltonian path; feedback vertex set; caterpillars; minimum node-deletion bipartite subgraph
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C99: Graph theory
Related Items
Independence and domination in polygon graphs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, On domination problems for permutation and other graphs, Dominating sets in perfect graphs, The complexity of domination problems in circle graphs