scientific article

zbMath0575.68069MaRDI QIDQ3694712

Andreas Brandstädt, Dieter Kratsch

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

spanning treeHamiltonian circuitcrossing numberdominating setpolynomial timeHamiltonian pathfeedback vertex setcaterpillarsminimum node-deletion bipartite subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ Cyclability in graph classes ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs ⋮ On domination problems for permutation and other graphs ⋮ Vertex deletion into bipartite permutation graphs ⋮ Induced star partition of graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Complete edge-colored permutation graphs ⋮ Star covers and star partitions of double-split graphs ⋮ Subgraph isomorphism in graph classes ⋮ Dominating sets in perfect graphs ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Independence and domination in polygon graphs ⋮ The complexity of domination problems in circle graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Vertex deletion into bipartite permutation graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ On connected dominating sets of restricted diameter