Optimal Linear Arrangement of Interval Graphs

DOI10.1007/11821069_24MaRDI QIDQ5756716zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Gregory Kucherov, Johanne Cohen

Publication date 5 September 2007

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

Full work available at URL https://doi.org/10.1007/11821069_24

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Linear Arrangement Problems and Interval Graphs
• Lower and upper bounds for the linear arrangement problem on interval graphs
• On optimal linear arrangements of trees
• An optimal time algorithm for minimum linear arrangement of chord graphs
• Minimum linear arrangement of chord graphs

Cited in

(20)

• Treewidth and minimum fill-in on permutation graphs in linear time
• Lower and upper bounds for the linear arrangement problem on interval graphs
• Linear time algorithms to solve the linear ordering problem for oriented tree based graphs
• Complexity of maximum cut on interval graphs
• On an ordering problem in weighted hypergraphs
• Complexity of maximum cut on interval graphs
• A note on minimum linear arrangement for BC graphs
• Minimum linear arrangement of the Cartesian product of optimal order graph and path
• Minimum Linear Arrangement of Series-Parallel Graphs
• An optimal time algorithm for minimum linear arrangement of chord graphs
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Linear Arrangement Problems and Interval Graphs
• Mixed search number and linear-width of interval and split graphs
• Malod and the Pascaline
• scientific article; zbMATH DE number 1161294 (Why is no real title available?)
• Semi-proper interval graphs
• Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges
• Mixed Search Number and Linear-Width of Interval and Split Graphs
• Maximum cut on interval graphs of interval count four is NP-complete
• The distance orientation problem

This page was built for publication: Optimal Linear Arrangement of Interval Graphs

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