Connecting Terminals and 2-Disjoint Connected Subgraphs

DOI10.1007/978-3-642-45043-3_36MaRDI QIDQ2864321zbMATH OpenOpenAlexFDO

Authors Jan Arne Telle, Yngve Villanger

Publication date 6 December 2013

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.2506

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Connectivity (05C40)

Abstract: Given a graph $G=(V,E)$ and a set of terminal vertices $T$ we say that a superset $S$ of $T$ is $T$-connecting if $S$ induces a connected graph, and $S$ is minimal if no strict subset of $S$ is $T$-connecting. In this paper we prove that there are at most $|VsetminusT|choose|T|-2cdot{3}^{frac|VsetminusT|3}$ minimal $T$-connecting sets when $|T|leqn/3$ and that these can be enumerated within a polynomial factor of this bound. This generalizes the algorithm for enumerating all induced paths between a pair of vertices, corresponding to the case $|T|=2$. We apply our enumeration algorithm to solve the {sc 2-Disjoint Connected Subgraphs} problem in time $O^{\ast }(1.7804^n)$, improving on the recent $O^{\ast }(1.933^n)$ algorithm of Cygan et al. 2012 LATIN paper.

Recommendations

• Algebraic connectivity and disjoint vertex subsets of graphs
• On two-connected subgraph polytopes
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Proper connection number 2, connectivity, and forbidden subgraphs
• Graphs with disjoint \(2\)-dominating sets
• Disjoint sub(di)graphs in digraphs
• Connected domination subdivision numbers of graphs
• Subgraphs decomposable into two trees and \(k\)-edge-connected subgraphs
• Non-separating subgraphs in highly connected graphs
• Connectivity, graph minors, and subgraph multiplicity

Cited in

(12)

• Enumerating Minimal Tropical Connected Sets
• Contracting bipartite graphs to paths and cycles
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• scientific article; zbMATH DE number 7561717 (Why is no real title available?)
• Path contraction faster than \(2^n\)
• Contracting bipartite graphs to paths and cycles
• Enumeration of minimal tropical connected sets
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\)
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Path Contraction Faster Than 2^n

This page was built for publication: Connecting Terminals and 2-Disjoint Connected Subgraphs

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