Profile minimization on triangulated triangles

DOI10.1016/S0012-365X(02)00450-8MaRDI QIDQ1861244zbMATH OpenFDO

Authors Yuqiang Guan, Kenneth L. Williams

Publication date 16 March 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00450-8

zbMATH Keywords

bandwidth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

Given a graph with \(n\) vertices, the profile minimization problem is to find a one-to-one function \(f\) from the vertex set to the integers \(1,\dots, n\) such that the sum of the differences \(f(v)-\min f(u)\), where \(u\) is a neighbour of \(v\), is minimized. The authors describe a polynomial algorithm to solve the profile minimization problem for triangulated triangles with side length \(d\). A triangulated triangle with side length \(d\) is a graph whose vertices are triples of nonnegative integers summing up to \(d\). Two vertices are adjacent if the corresponding triples agree in one coordinate of the triple and differ by 1 in the other two coordinates.

Recommendations

• The Profile Minimization Problem in Trees
• One strike against the min-max degree triangulation problem
• Profile minimization problem for matrices and graphs
• Profile minimization on compositions of graphs
• Fixed-Parameter Complexity of Minimum Profile Problems

Cited in

(4)

• On the profile of the corona of two graphs
• A variable neighborhood search and simulated annealing hybrid for the profile minimization problem
• Profile minimization on products of graphs
• The Profile Minimization Problem in Trees

This page was built for publication: Profile minimization on triangulated triangles

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