Live briefing
Everything about Cutwidth
Property in graph theory
In graph theory, the cutwidth of an undirected graph is the smallest integer with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered, then for every, the number of edges with and is at most. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: CutwidthA 5-minute orientation
- Skim a recent paper: Breakout local search for the cyclic cutwidth minimization problemInfluential work since 2022
- Read the landmark paper: Variable Formulation Search for the Cutwidth Minimization ProblemCited 71 times
- Go sideways: Graph bandwidthA closely related topic
- Go sideways: Carving widthA closely related topic
📖 Definitions
Noun The minimum number of edges that cross any cut between lower-numbered and higher-numbered vertices in an optimal linear arrangement of the vertices of a graph.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Variable Formulation Search for the Cutwidth Minimization Problem
Tree-width, path-width, and cutwidth
Cutwidth I: A linear time fixed parameter algorithm
Graphs with small bandwidth and cutwidth
Scatter search for the cutwidth minimization problem
On the Cutwidth and the Topological Bandwidth of a Tree
Cutwidth II: Algorithms for partial w-trees of bounded degree
The cyclic cutwidth of trees
🆕 Influential since 2022
Breakout local search for the cyclic cutwidth minimization problem
Strong SDP based bounds on the cutwidth of a graph
Polynomial Formal Verification of Multi-Valued Approximate Circuits Within Constant Cutwidth
Edge-maximal graphs with cutwidth at most three
Structures of Critical Nontree Graphs with Cutwidth Four
📚 Books worth reading
Open Library didn't respond; try again in a moment.
🔗 Related topics
- Graph bandwidth In graph theory, the graph bandwidth problem may be visualized as placing the vertices of a given graph at distinct integer positions along the number…
- Carving width In graph theory, the carving width of a graph is a number, defined from the graph, that describes the number of edges separating the clusters in a hierarchical…
- Pathwidth In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number…
- Treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest…
- Indifference graph In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting…
- Tree-depth In graph theory, the tree-depth of a connected undirected graph G {\displaystyle G} is a numerical invariant of G {\displaystyle G} , the minimum height…
- 1-planar graph In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing…
- Queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using…