The vertex separation number of a graph equals its path-width
type: Item
instance of: scholarly article
title: The vertex separation number of a graph equals its path-width
zbMATH Open document ID: 0764.68121
DOI: 10.1016/0020-0190(92)90234-M
author: Nancy G. Kinnersley
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 92142
zbMATH Keywords: computational complexity
zbMATH Keywords: graph's vertex separation number
zbMATH Keywords: path-width
zbMATH Keywords: decision algorithms
zbMATH Keywords: tree obstructions
MaRDI profile type: Publication
cites work: The vertex separation and search number of a graph
cites work: Nonconstructive advances in polynomial-time complexity
cites work: Nonconstructive tools for proving polynomial-time decidability
cites work: Interval graphs and searching
cites work: Searching and pebbling
cites work: Recontamination does not help to search a graph
cites work: Black-white pebbles and graph separation
cites work: Q4159394
cites work: Disjoint Paths—A Survey
cites work: Graph minors. X: Obstructions to tree-decomposition
full work available at URL: 0020-0190(92)90234-m
OpenAlex ID: W2052867211
Recommended article: The total vertex separation number of a graph
Recommended article: The cutwidth of a graph and the vertex separation number of the line graph
Recommended article: The total vertex separation number and profile of a graph
Recommended article: On the path separation number of graphs
Recommended article: The vertex detour number of a graph
Recommended article: On the separation number of a graph
Recommended article: Path Separability of Graphs
Recommended article: Q3104343
Recommended article: Q3561269
description: scientific article; zbMATH DE number 92142