Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time

2003/04/01 by K. Skodinis, Konstantin Skodinis · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Artificial intelligence #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Graph #Linear programming #Mathematics #Time complexity #Tree (set theory) #Vertex (graph theory)

paper · doi:10.1016/s0196-6774(02)00225-0

crossref issued 2003/04/01 · crossref published 2003/04/01 · crossref published-print 2003/04/01 · openalex publication_date 2003/04/01 · crossref created 2003/05/12 · crossref deposited 2019/03/21 · openalex created_date 2025/10/10 · crossref indexed 2025/10/11 · openalex updated_date 2026/07/28

Citations

• Searching and pebbling
• Graph minors. I. Excluding a forest
• 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

Cited by

• Pathwidth of outerplanar graphs
• A Distributed Algorithm for Computing the Node Search Number in Trees
• Pathwidth of Circular-Arc Graphs
• Pathwidth [wikipedia]