Parameterized Algorithms and Hardness Results for Some Graph Motif Problems

DOI10.1007/978-3-540-69068-9_6MaRDI QIDQ3506940zbMATH OpenOpenAlexWikidataFDO

Authors Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier

Publication date 17 June 2008

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL http://espace.cdu.edu.au/view/cdu:9643

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• The graph motif problem parameterized by the structure of the input graph
• The graph motif problem parameterized by the structure of the input graph
• Graph motif problems parameterized by dual
• Graph motif problems parameterized by dual
• Some results on more flexible versions of Graph Motif

Cites work

• Algorithm engineering for color-coding with applications to signaling pathway detection
• Color-coding
• Depth-First Search and Linear Graph Algorithms
• Fourier meets M\"{o}bius: fast subset convolution
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Perfect Code is \(W[1]\)-complete
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs

Cited in

(21)

• Finding and counting vertex-colored subtrees
• Algorithms for topology-free and alignment network queries
• The parameterised complexity of counting connected subgraphs and graph motifs
• Some results on more flexible versions of Graph Motif
• The graph motif problem parameterized by the structure of the input graph
• Improved parameterized algorithms for network query problems
• Constrained multilinear detection and generalized graph motifs
• Colourful components in \(k\)-caterpillars and planar graphs
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Improved parameterized algorithms for network query problems
• On structural parameterizations of graph motif and chromatic number
• Finding approximate and constrained motifs in graphs
• Deterministic subgraph detection in broadcast CONGEST
• Maximum Motif Problem in Vertex-Colored Graphs
• Confronting intractability via parameters
• Graph motif problems parameterized by dual
• Engineering motif search for large motifs
• Complexity issues in vertex-colored graph pattern matching
• The graph motif problem parameterized by the structure of the input graph
• Graph motif problems parameterized by dual
• Upper and lower bounds for finding connected motifs in vertex-colored graphs

This page was built for publication: Parameterized Algorithms and Hardness Results for Some Graph Motif Problems

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