On Three Graph Layout Problems - Couverture souple

Muradian, David

Couverture souple

ISBN 10 : 6202053852 ISBN 13 : 9786202053853

Editeur : LAP LAMBERT Academic Publishing, 2018

Synopsis

The bandwidth minimization problem for graphs was first stated in 1966 by Harper, where the problem was solved for hypercubes. Finding the bandwidth of an arbitrary graph is an NP-complete problem and it remains NP-complete for many simple structures, e.g. for cyclic caterpillars with hair length at most 1, graphs in which the removal of all pendant vertices results in a simple cycle. There are only few classes of graphs for which an efficient solution to the bandwidth problem is known. Classes of graphs whose bandwidth can be computed efficiently are butterflies, chain graphs, caterpillars with hair length at most 2. Another nontrivial class, for which the problem was solved efficiently, is the class of interval graphs, graphs which are the intersection graphs of a family of intervals over the real line. The first polynomial algorithm for interval graphs was given in 1986 by the author. It was published in the Reports of NAS RA, where the algorithm is described in detail, and besides a brief proof of its correctness is done. Since this result was independently obtained and published earlier we consider reasonable publishing the full proof of our algorithm’s correctness.

Détails de l'édition

• Éditeur: LAP LAMBERT Academic Publishing
• Date d'édition: 2018
• Langue: anglais
• ISBN 10: 6202053852
• ISBN 13: 9786202053853
• Reliure: Broché
• Nombre de pages: 64
• Coordonnées du fabricant: non disponible
• Personne responsable: KreGa Onlinehandel GmbH; 4950000000000; info@krega-onlinehandel.de; ; Birkenweg 31; Brakel; 33034; Allemagne