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

permutationmodular decomposition\(PQ\)-treecommon interval

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(16)

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

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)