scientific article; zbMATH DE number 4047762
[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.
- Algorithm for solving a problem on optimal linear ordering
- Optimal vertex ordering of graphs
- Vertex ordering and partitioning problems for random spatial graphs.
- On the complexity of a linear ordering of weighted directed acyclic graphs
- Efficient reassembling of graphs. I: The linear case
- On approximability of linear ordering and related NP-optimization problems on graphs (extended abstract)
- scientific article; zbMATH DE number 3981183 (Why is no real title available?)
- Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges
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)