scientific article; zbMATH DE number 468640
From MaRDI portal
Publication:4272117
zbMath0804.05066MaRDI QIDQ4272117
Dmitry V. Korobitsyn, Vladimir E. Alekseev
Publication date: 9 January 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
complexityNP-harddominating setpolynomial timelongest pathindependent set problemforbidden graphshereditary classes
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
Boundary classes of graphs for the dominating set problem ⋮ Independent sets in graphs without subtrees with many leaves ⋮ New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ Unnamed Item ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Polynomial algorithm for finding the largest independent sets in graphs without forks ⋮ Minimal antichains in well-founded quasi-orders with an application to tournaments
This page was built for publication:
