On subbetweennesses of trees: hardness, algorithms, and characterizations

DOI10.1016/j.camwa.2011.10.056zbMath1235.05044OpenAlexW2063970303MaRDI QIDQ2429121

Vinícius Fernandes dos Santos, Dieter Rautenbach, Philipp Matthias Schäfer, Jayme Luiz Szwarcfiter

Publication date: 22 April 2012

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.camwa.2011.10.056

zbMATH Keywords

treesshortest pathsbetweennesstotal ordering problem

Mathematics Subject Classification ID

Applications of graph theory (05C90) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Finite Sholander trees, trees, and their betweenness
• Axiomatic characterization of the interval function of a graph
• Tree representations of ternary relations
• Sylvester-Gallai theorem and metric betweenness
• Intervals and steps in a connected graph
• Simple linear time approximation algorithm for betweenness
• The interval function of a connected graph and road systems
• Zur Axiomatik der teilweise geordneten Mengen
• Antimatroids, Betweenness, Convexity
• Représentations en arbre de proximités relatives
• Total Ordering Problem
• A Geometric Approach to Betweenness
• Axiomatization and Undecidability Results for Metrizable Betweeness Relations
• Constraint Satisfaction Problems on Intervals and Lengths
• Ordinal embeddings of minimum relaxation
• Betweenness and Comparability Obtained from Binary Relations
• Trees, Lattices, Order, and Betweenness

This page was built for publication: On subbetweennesses of trees: hardness, algorithms, and characterizations