Extracting constrained 2-interval subsets in 2-interval sets

DOI10.1016/J.TCS.2007.07.002MaRDI QIDQ2456375zbMATH OpenOpenAlexFDO

Authors Guillaume Blin, Guillaume Fertin, Stéphane Vialette

Publication date 18 October 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.07.002

zbMATH Keywords

2-intervalscomputational complexitypattern matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Constrained hitting set problem with intervals
• The interval subset sum problem
• scientific article; zbMATH DE number 3967928
• New bounds for subset selection from conic relaxations
• scientific article; zbMATH DE number 1315280
• scientific article; zbMATH DE number 2087043
• A constrained two-stage submodular maximization
• Publication:5751991
• Principles and Practice of Constraint Programming – CP 2004
• Max-Min Problems of Searching for Two Disjoint Subsets

Cites work

• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Approximating the 2-interval pattern problem
• Combinatorial Pattern Matching
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Extremal Values of the Interval Number of a Graph
• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• scientific article; zbMATH DE number 2185647 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1954383 (Why is no real title available?)
• scientific article; zbMATH DE number 2087043 (Why is no real title available?)
• scientific article; zbMATH DE number 2087047 (Why is no real title available?)
• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Incidence matrices and interval graphs
• On computing the length of longest increasing subsequences
• On double and multiple interval graphs
• On the computational complexity of 2-interval pattern matching problems
• Optimization problems in multiple-interval graphs
• Pattern Matching and Pattern Discovery Algorithms for Protein Topologies
• Recognizing graphs with fixed interval number is NP-complete
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring

Cited in

(11)

• On the parameterized complexity of multiple-interval graph problems
• On two open problems of 2-interval patterns
• On recovering syntenic blocks from comparative maps
• Parameterized complexity of two-interval pattern problem
• scientific article; zbMATH DE number 2087043 (Why is no real title available?)
• Combinatorial Pattern Matching
• On Recovering Syntenic Blocks from Comparative Maps
• Algorithms and Computation
• Parameterized complexity of two-interval pattern problem
• Finding common structured patterns in linear graphs
• Improved algorithms for largest cardinality 2-interval pattern problem

This page was built for publication: Extracting constrained 2-interval subsets in 2-interval sets

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