Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs

DOI10.1137/060651331MaRDI QIDQ3394985zbMATH OpenOpenAlexFDO

Authors Anne Bergeron, Cedric Chauve, Fabien De Montgolfier, Mathieu Raffinot

Publication date 20 August 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/060651331

zbMATH Keywords

\(PQ\)-treecommon intervalmodular decompositionpermutation

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Algorithms – ESA 2005
• Algorithms and Computation
• Common intervals of multiple permutations
• scientific article; zbMATH DE number 1786460
• Common intervals of trees

Cited in

(18)

• Fully dynamic representations of interval graphs
• Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints
• Fast algorithms to enumerate all common intervals of two permutations
• \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
• A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
• Complete edge-colored permutation graphs
• Average-case analysis of perfect sorting by reversals
• Average-Case Analysis of Perfect Sorting by Reversals
• New applications of interval generators to genome comparison
• scientific article; zbMATH DE number 1786460 (Why is no real title available?)
• A survey of the algorithmic aspects of modular decomposition
• Extending common intervals searching from permutations to sequences
• Common intervals of multiple permutations
• Algorithms – ESA 2005
• Algorithms and Computation
• Modules and PQ-trees in Robinson spaces
• Twin-width one

This page was built for publication: Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs

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