Fast algorithms for identifying maximal common connected sets of interval graphs

DOI10.1016/J.DAM.2006.02.005MaRDI QIDQ2499592zbMATH OpenOpenAlexFDO

Authors Fabien Coulon, Mathieu Raffinot

Publication date 14 August 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.02.005

zbMATH Keywords

common connected setcomparative genomicsinterval graphumbrella-free ordering

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Genetics and epigenetics (92D10)

Recommendations

• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Parallel algorithms for connectivity problems on interval graphs
• Graph-Based Representations in Pattern Recognition

Cites work

• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• A unified approach to domination problems on interval graphs
• An algorithmic view of gene teams
• Combinatorial Pattern Matching
• Fast algorithms to enumerate all common intervals of two permutations
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 1786460 (Why is no real title available?)
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Partitioning a graph in \(O(|A|\log_ 2|V|)\)
• Representation of a finite graph by a set of intervals on the real line
• Three Partition Refinement Algorithms

Cited in

(4)

• Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints
• Competitive graph searches
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Combinatorial Pattern Matching

This page was built for publication: Fast algorithms for identifying maximal common connected sets of interval graphs

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