Faster exact algorithms for some terminal set problems

DOI10.1016/J.JCSS.2017.04.003MaRDI QIDQ2361353zbMATH OpenOpenAlexFDO

Authors Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh

Publication date 30 June 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL http://pure-oai.bham.ac.uk/ws/files/90877277/J8_Faster_Exact_Algorithms.pdf

zbMATH Keywords

exact exponential time algorithmsfeedback vertex setmultiway cutterminal set problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Faster exact algorithms for some terminal set problems
• Simple and improved parameterized algorithms for multiterminal cuts
• Algorithms for Multiterminal Cuts
• Subset feedback vertex set on graphs of bounded independent set size
• SOFSEM 2006: Theory and Practice of Computer Science

Cites work

• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• Algorithms for maximum independent sets
• An improved parameterized algorithm for the minimum node multiway cut problem
• Enumerating minimal subset feedback vertex sets
• Exact Algorithms for Maximum Independent Set
• Exact Computation of Maximum Induced Forest
• Exact exponential algorithms.
• Faster deterministic \textsc{Feedback Vertex Set}
• Feedback vertex set on AT-free graphs
• Finding a maximum induced degenerate subgraph faster than \(2^{n}\)
• Finding induced subgraphs via minimal triangulations
• Improved upper bounds for vertex cover
• König Deletion Sets and Vertex Covers above the Matching Size
• Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• Multiway cuts in node weighted graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Parameterized graph separation problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Solving multicut faster than \(2^{n }\)
• Subset feedback vertex sets in chordal graphs
• The complexity of generalized clique covering
• The maximum k-colorable subgraph problem for chordal graphs
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(14)

• Subset feedback vertex set on graphs of bounded independent set size
• Faster exact algorithms for some terminal set problems
• Irredundant Set Faster Than O(2 n )
• scientific article; zbMATH DE number 1405801 (Why is no real title available?)
• Subset feedback vertex set on graphs of bounded independent set size
• Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
• Computing subset transversals in \(H\)-free graphs
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Exponential-time approximation schemes via compression
• Solving directed multiway cut faster than 2ⁿ
• Subset feedback vertex set and subset vertex cover on AT-free graphs
• Faster exponential algorithms for cut problems via geometric data structures

This page was built for publication: Faster exact algorithms for some terminal set problems

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