Connected (s,t)-vertex separator parameterized by chordality

DOI10.7155/JGAA.00377zbMATH Open1326.05154OpenAlexW2397396903MaRDI QIDQ3454522FDOQ3454522

Authors: N. S. Narayanaswamy, N. Sadagopan 

Publication date: 25 November 2015

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00377

Recommendations

• Some results on connected vertex separators
• On the parameterized complexity of finding separators with non-hereditary properties
• On the parameterized complexity of finding separators with non-hereditary properties
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• A Separator Theorem for Chordal Graphs

zbMATH Keywords

chordality dichotomyquasi-polynomial Las Vegas algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• Hamiltonicity in Split Graphs - A Dichotomy
• On the parameterized complexity of finding separators with non-hereditary properties
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
• Some results on connected vertex separators
• Computation in causal graphs

This page was built for publication: Connected \((s,t)\)-vertex separator parameterized by chordality

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