Topological Bandwidth
From MaRDI portal
Publication:3691781
DOI10.1137/0606044zbMath0573.05052OpenAlexW4248251133MaRDI QIDQ3691781
F. S. Makedon, Ivan Hal Sudborough, Christos H. Papadimitriou
Publication date: 1985
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0606044
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)
Related Items
Efficient reassembling of graphs. I: The linear case, Decomposability of a class of \(k\)-cutwidth critical graphs, On embedding graphs in trees, Branch and bound for the cutwidth minimization problem, Optimal labelling of unit interval graphs, Congestion optimale du plongement de l’hypercube $H (n)$ dans la chaîne $P(2^n)$, Min Cut is NP-complete for edge weighted trees, Graphs with small bandwidth and cutwidth, Helicopter search problems, bandwidth and pathwidth, Fast searching games on graphs, Fast searching on \(k\)-combinable graphs, Edge searching and fast searching with constraints, Fast Searching on Complete k-partite Graphs, Fast edge searching and fast searching on graphs, Fast searching on cactus graphs, A variation on the min cut linear arrangement problem, The theory of guaranteed search on graphs, Fast Searching on Cartesian Products of Graphs, An annotated bibliography on guaranteed graph searching, The fast search number of a Cartesian product of graphs, Scatter search for the cutwidth minimization problem, A polynomial algorithm for recognizing bounded cutwidth in hypergraphs, Unnamed Item, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, The treewidth of line graphs, The fast search number of a complete \(k\)-partite graph, On the domination search number, On minimizing width in linear layouts, Nondeterministic graph searching: from pathwidth to treewidth, Edge searching weighted graphs, A partial k-arboretum of graphs with bounded treewidth, Standard directed search strategies and their applications, Linear graph grammars: Power and complexity, Edge and node searching problems on trees, On the Cutwidth and the Topological Bandwidth of a Tree, Searching expenditure and interval graphs, Synchronous context-free grammars and optimal linear parsing strategies, On the bandwidth of the Kneser graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bandwidth constraints on problems complete for polynomial time
- Black-white pebbles and graph separation
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- The NP-completeness of the bandwidth minimization problem
- Bandwidth and pebbling
- One-dimensional logic gate assignment and interval graphs
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- On the Cutwidth and the Topological Bandwidth of a Tree
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
- The bandwidth problem for graphs and matrices—a survey
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
- Complexity Results for Bandwidth Minimization
- On arithmetic expressions and trees
