Show simple item record

dc.contributor.authorKfoury, Assafen_US
dc.contributor.authorMirzaei, Saberen_US
dc.date.accessioned2017-04-26T18:43:36Z
dc.date.available2017-04-26T18:43:36Z
dc.date.issued2015-09-01
dc.identifier.citationKfoury, Assaf; Mirzaei, Saber. Linear Arrangement of Halin Graphs. Technical Report BU-CS-TR 2015-012, Computer Science Department, Boston University, September 1, 2015.
dc.identifier.urihttps://hdl.handle.net/2144/21776
dc.description.abstractWe study the Optimal Linear Arrangement (OLA) problem of Halin graphs, one of the simplest classes of non-outerplanar graphs. We present several properties of OLA of general Halin graphs. We prove a lower bound on the cost of OLA of any Halin graph, and define classes of Halin graphs for which the cost of OLA matches this lower bound. We show for these classes of Halin graphs, OLA can be computed in nlog n, where n is the number of vertices.en_US
dc.language.isoen_US
dc.publisherComputer Science Department, Boston Universityen_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2015-012
dc.subjectHalin graphsen_US
dc.subjectOptimal Linear Arrangement (OLA)en_US
dc.titleLinear arrangement of Halin graphsen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record