Exact exponential algorithms to find a tropical connected set of minimum size

DOI10.1007/978-3-319-13524-3_13MaRDI QIDQ2946015zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Exact exponential algorithms to find tropical connected sets of minimum size
• Enumerating Minimal Tropical Connected Sets
• Connected tropical subgraphs in vertex-colored graphs

Cites work

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

Cited in

(3)

• Enumeration of minimal tropical connected sets
• Enumerating Minimal Tropical Connected Sets
• Exact exponential algorithms to find tropical connected sets of minimum size

This page was built for publication: Exact exponential algorithms to find a tropical connected set of minimum size

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