The weighted sitting closer to friends than enemies problem in the line

DOI10.1007/S10878-022-00953-ZMaRDI QIDQ2099388zbMATH OpenOpenAlexFDO

Authors Julio Aracena, Christopher Thraves Caro

Publication date 23 November 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.11812

zbMATH Keywords

metric spacesRobinsonian matricesSeriation problemthe SCFE problemvalid distance drawingsweighted graphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) (n)-dimensional polytopes (52B11) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• Sitting closer to friends than enemies, revisited
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Sitting closer to friends than enemies, revisited
• The seriation problem in the presence of a double Fiedler value

Cites work

• A structural characterization for certifying Robinsonian matrices
• An optimal algorithm to recognize Robinsonian dissimilarities
• Can everybody sit closer to their friends than their enemies?
• Combinatorial data analysis. Optimization by dynamic programming
• Embedding signed graphs in the line
• scientific article; zbMATH DE number 3843553 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 2231543 (Why is no real title available?)
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• Recognition of Robinsonian dissimilarities
• Robinsonian matrices: recognition challenges
• Seriation and matrix reordering methods: An historical overview
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
• Sitting closer to friends than enemies, revisited
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The dimension of valid distance drawings of signed graphs
• The weighted sitting closer to friends than enemies problem in the line

Cited in

(5)

• The weighted sitting closer to friends than enemies problem in the line
• Sitting closer to friends than enemies, revisited
• Sitting closer to friends than enemies, revisited
• The Weighted Sitting Closer to Friends than Enemies Problem in the Line
• Multi-armed bandit for the cyclic minimum sitting arrangement problem

This page was built for publication: The weighted sitting closer to friends than enemies problem in the line

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