Parameterized Algorithms and Hardness Results for Some Graph Motif Problems

DOI10.1007/978-3-540-69068-9_6zbMath1143.68501OpenAlexW1602427246WikidataQ57359911 ScholiaQ57359911MaRDI QIDQ3506940

Nadja Betzler, Christian Komusiewicz, Michael R. Fellows, 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

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

Related Items (15)

Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ Improved Parameterized Algorithms for Network Query Problems ⋮ Improved parameterized algorithms for network query problems ⋮ Finding and counting vertex-colored subtrees ⋮ Confronting intractability via parameters ⋮ Finding Approximate and Constrained Motifs in Graphs ⋮ Algorithms for topology-free and alignment network queries ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Maximum Motif Problem in Vertex-Colored Graphs ⋮ Unnamed Item ⋮ Some results on more flexible versions of Graph Motif ⋮ Constrained multilinear detection and generalized graph motifs

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Perfect Code is \(W[1\)-complete]
• Fourier meets M\"{o}bius: fast subset convolution
• Color-coding
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Depth-First Search and Linear Graph Algorithms

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