scientific article; zbMATH DE number 4047762

From MaRDI portal
Publication:3784098





[For the entire collection see Zbl 0585.00007.] Let be G a graph and \({\mathfrak F}^ a \)given functional. The problem to determine a numeration f of vertices in such a way that \({\mathfrak F}\) becomes a minimum (or maximum) is called a linear ordering problem of graphs. In this note are described four examples respectively applications: 1. The NP-complete bandwidth problem for finite undirected simple graphs. Using the associated adjacency matrix of G arises the known bandwidth problem for matrices. 2. The bandwidth-sum-problem which also is NP-complete. 3. The bandwidth-K-problem belonging to the class of problems which can be solved in polynomial time. 4. A new linear ordering problem follows by using a suitable valuation \(g_ f\) of the edges which yields from a proper numeration f of the vertices of a finite undirected simple graph G; this is called Minimum- weight-problem. \(g_ f\) is called the weight of an edge with respect to f and the maximal \(g_ f\) in G is called the weight g(G) of G with respect to f. For special graphs G are mentioned some relations between g(G) and the number of their vertices respectively the number of inner stability of G. Finally are still mentioned the following results and references to its proof: This problem is NP-hard.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3784098)