Cutwidth (original) (raw)
In graph theory, the cutwidth of an undirected graph G = (V, E) is the smallest integer k with the following property: there is an ordering {v1, …, vn} of the vertices of G, such that for every l = 1, …, n – 1, there are at most k edges with one endpoint in {v1, …, vl} and the other endpoint in {vl + 1, …, vn} .
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, the cutwidth of an undirected graph G = (V, E) is the smallest integer k with the following property: there is an ordering {v1, …, vn} of the vertices of G, such that for every l = 1, …, n – 1, there are at most k edges with one endpoint in {v1, …, vl} and the other endpoint in {vl + 1, …, vn} . (en) |
| dbo:wikiPageID | 69798178 (xsd:integer) |
| dbo:wikiPageLength | 1371 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1111673184 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pathwidth dbr:Undirected_graph dbc:Graph_invariants dbc:Integers dbr:Treewidth dbr:Graph_theory dbr:Integer dbr:Vertex_(graph_theory) |
| dbp:wikiPageUsesTemplate | dbt:Combin-stub dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Sub |
| dct:subject | dbc:Graph_invariants dbc:Integers |
| rdfs:comment | In graph theory, the cutwidth of an undirected graph G = (V, E) is the smallest integer k with the following property: there is an ordering {v1, …, vn} of the vertices of G, such that for every l = 1, …, n – 1, there are at most k edges with one endpoint in {v1, …, vl} and the other endpoint in {vl + 1, …, vn} . (en) |
| rdfs:label | Cutwidth (en) |
| owl:sameAs | wikidata:Cutwidth https://global.dbpedia.org/id/GDwM4 |
| prov:wasDerivedFrom | wikipedia-en:Cutwidth?oldid=1111673184&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Cutwidth |
| is dbo:wikiPageWikiLink of | dbr:Queue_number dbr:Arc_diagram dbr:Pathwidth dbr:Circular_layout |
| is foaf:primaryTopic of | wikipedia-en:Cutwidth |