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

DOI10.1137/060651331zbMath1190.05044OpenAlexW2091032904MaRDI QIDQ3394985

Mathieu Raffinot, Anne Bergeron, Cedric Chauve, Fabien de Montgolfier

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

permutationmodular decomposition\(PQ\)-treecommon interval

Mathematics Subject Classification ID

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

Related Items (10)

AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS ⋮ A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs ⋮ Complete edge-colored permutation graphs ⋮ New applications of interval generators to genome comparison ⋮ Fully dynamic representations of interval graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ \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 ⋮ Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints ⋮ Average-Case Analysis of Perfect Sorting by Reversals

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