Computing Optimal Linear Layouts of Trees in Linear Time

2000/01/01 by K. Skodinis, Konstantin Skodinis · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Artificial intelligence #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Enhanced Data Rates for GSM Evolution #Graph #Interval (graph theory) #Linear programming #Mathematical optimization #Mathematics #Node (physics) #Running time #Theoretical computer science #Time complexity #Tree (set theory) #Vertex (graph theory)

paper · doi:10.1007/3-540-45253-2_37

crossref issued 2000/01/01 · crossref published 2000/01/01 · crossref published-print 2000/01/01 · openalex publication_date 2000/01/01 · crossref published-online 2003/02/11 · crossref created 2007/11/13 · crossref deposited 2019/02/25 · crossref indexed 2024/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Citations

• Searching and pebbling
• Graph minors. I. Excluding a forest
• Interval graphs and seatching
• The vertex separation number of a graph equals its path-width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Black-white pebbles and graph separation
• The Vertex Separation and Search Number of a Graph
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

Cited by

• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Approximation of pathwidth of outerplanar graphs
• Pathwidth [wikipedia]