On minimizing width in linear layouts

DOI10.1016/0166-218X(89)90016-4zbMath0715.05012WikidataQ128127009 ScholiaQ128127009MaRDI QIDQ751660

Fillia Makedon, Ivan Hal Sudborough

Publication date: 1989

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

bandwidthcomputationcutwidthsearch numberfinite undirected graphs

Mathematics Subject Classification ID

Other designs, configurations (05B30)

Related Items

Minimal congestion trees ⋮ On Cutwidth Parameterized by Vertex Cover ⋮ Branch and bound for the cutwidth minimization problem ⋮ Linear layouts of generalized hypercubes ⋮ On the monotonicity of games generated by symmetric submodular functions. ⋮ The cutwidth of trees with diameters at most 4 ⋮ An annotated bibliography on guaranteed graph searching ⋮ Distributed chasing of network intruders ⋮ On cutwidth parameterized by vertex cover ⋮ LINEAR LAYOUT OF GENERALIZED HYPERCUBES ⋮ Minimal cutwidth linear arrangements of abelian Cayley graphs ⋮ Graph parameters measuring neighbourhoods in graphs-bounds and applications ⋮ Cooperative exploration and protection of a workspace assisted by information networks ⋮ Scatter search for the cutwidth minimization problem ⋮ Multistart search for the cyclic cutwidth minimization problem ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ Graph classes and the switch Markov chain for matchings ⋮ Tree-width, path-width, and cutwidth ⋮ On the domination search number ⋮ Nondeterministic graph searching: from pathwidth to treewidth ⋮ Edge and node searching problems on trees ⋮ One-visibility cops and robber on trees: optimal cop-win strategies ⋮ Bandwidth and density for block graphs ⋮ Searching expenditure and interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• One-dimensional logic gate assignment and interval graphs
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Topological Bandwidth
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• A polynomial algorithm for the min-cut linear arrangement of trees
• The complexity of searching a graph
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• Complexity Results for Bandwidth Minimization
• Recontamination does not help to search a graph