Black-white pebbles and graph separation

DOI10.1007/BF00264496zbMath0454.68027OpenAlexW2063019820WikidataQ59445249 ScholiaQ59445249MaRDI QIDQ1149765

Thomas Lengauer

Publication date: 1981

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00264496

zbMATH Keywords

separatorlinear arrangement problemsanalysis of storage requirements for nondeterministic computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (19)

Improved self-reduction algorithms for graphs with bounded treewidth ⋮ Vertex ordering and partitioning problems for random spatial graphs. ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Variable neighborhood search for the vertex separation problem ⋮ Min Cut is NP-complete for edge weighted trees ⋮ Graph layout problems ⋮ Helicopter search problems, bandwidth and pathwidth ⋮ An Application of Generalized Tree Pebbling to Sparse Matrix Factorization ⋮ Connections between cutting-pattern sequencing, VLSI design, and flexible machines ⋮ On integer linear programs for treewidth based on perfect elimination orderings ⋮ Narrowness, pathwidth, and their application in natural language processing ⋮ The vertex separation number of a graph equals its path-width ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay. ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ The treewidth of line graphs ⋮ Searching and pebbling ⋮ An experimental comparison of Variable Neighborhood Search variants for the minimization of the vertex-cut in layout problems ⋮ Topological Bandwidth

This page was built for publication: Black-white pebbles and graph separation