Exact exponential algorithms to find tropical connected sets of minimum size

DOI10.1016/j.tcs.2017.03.003zbMath1369.05190OpenAlexW2596652947WikidataQ115566734 ScholiaQ115566734MaRDI QIDQ527400

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

Publication date: 11 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.03.003

zbMATH Keywords

algorithmsexact exponential algorithmscolored graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Enumeration of minimal tropical connected sets

Cites Work

• Unnamed Item
• Constrained multilinear detection and generalized graph motifs
• Finding approximate and constrained motifs in graphs
• Constrained multilinear detection for faster functional motif discovery
• Complexity issues in vertex-colored graph pattern matching
• An exact algorithm for connected red-blue dominating set
• Quadratic kernelization for convex recoloring of trees
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Improved approximation algorithm for convex recoloring of trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Finding and counting vertex-colored subtrees
• On the Kernelization Complexity of Colorful Motifs
• Triangulating Vertex-Colored Graphs
• Graph-Theoretic Concepts in Computer Science
• On the complexity of \(k\)-SAT