Computing optimal linear layouts of trees in linear time

DOI10.1007/3-540-45253-2_37MaRDI QIDQ2753956zbMATH OpenFDO

Authors Konstantin Skodinis

Publication date 11 November 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45253-2_37

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• A linear-time algorithm for constructing an optimal node-search strategy of a tree
• Parameterized and Exact Computation
• On optimal linear arrangements of trees
• Edge and node searching problems on trees

Cited in

(21)

• On finding optimal and near-optimal lineal spanning trees
• A linear-time algorithm for the feasibility of pebble motion on trees
• Linear-time construction of treaps and Cartesian trees
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Linear time algorithms on mirror trees
• Worst-case optimal tree layout in external memory
• The tree inclusion problem
• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• Variable neighborhood search for the vertex separation problem
• A linear-time algorithm for constructing an optimal node-search strategy of a tree
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• A linear algorithm for compact box-drawings of trees
• Linear layouts in submodular systems
• Neighbourhood-width of trees
• A linear time algorithm for the feasibility of pebble motion on trees
• Slicing tree's geometric potential: an indicator for layout problems based on slicing tree structure
• Computing the vertex separation of unicyclic graphs
• Navigating Forest Straight-Line Programs in Constant Time
• On optimal linear arrangements of trees
• Linear-time algorithms for problems on planar graphs with fixed disk dimension
• Distributed chasing of network intruders

This page was built for publication: Computing optimal linear layouts of trees in linear time

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