Algorithms on subgraph overlap graphs

DOI10.1142/S1793830914500189MaRDI QIDQ2875683zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

Publication date 11 August 2014

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830914500189

zbMATH Keywords

overlap graphpolynomial time algorithmsubgraph filament graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Analysis of algorithms (68W40)

Review text

In the paper under review, the author deals with subgraph overlap graphs and shows that, under some additional mild assumptions, these graphs are equivalent to subgraph filament graphs. The latter type of graphs is used in applications, for instance for analysis of protein interactions and occurrence of genes in the DNA. The author proves that on this class of subgraphs several classical problems can be solved with polynomial time algorithms.

Recommendations

• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• Algorithms on Subtree Filament Graphs
• Sublinear graph approximation algorithms
• A parameterized algorithm for packing overlapping subgraphs
• On -overlap graphs
• Algorithmic aspects of total k-subdomination in graphs
• scientific article; zbMATH DE number 3910446
• A note on algebraic techniques for subgraph detection
• Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity
• On linear algebraic algorithms for the subgraph matching problem and its variants

Cited in

(10)

• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
• Algorithms on Subtree Filament Graphs
• Equivalence of the filament and overlap graphs of subtrees of limited trees
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Computation of overlapping classes in a graph: application to protein-protein interactions networks
• Recognising the overlap graphs of subtrees of restricted trees is hard
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs

This page was built for publication: Algorithms on subgraph overlap graphs

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