Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size

DOI10.1007/978-3-319-13524-3_13zbMath1456.68228OpenAlexW1576211977MaRDI QIDQ2946015

Manfred Cochefert, Mathieu Chapelle, Mathieu Liedloff, Dieter Kratsch, Romain Letourneur

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13524-3_13

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (2)

Enumeration of minimal tropical connected sets ⋮ Enumerating Minimal Tropical Connected Sets

Cites Work

• Unnamed Item
• Complexity issues in vertex-colored graph pattern matching
• Exact exponential algorithms.
• An exact algorithm for connected red-blue dominating set
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Finding and counting vertex-colored subtrees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On the Kernelization Complexity of Colorful Motifs
• Triangulating Vertex-Colored Graphs
• STACS 2004
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Graph-Theoretic Concepts in Computer Science
• On the complexity of \(k\)-SAT

This page was built for publication: Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size