Chordless paths through three vertices

DOI10.1016/j.tcs.2005.10.021zbMath1086.68102OpenAlexW2144784192MaRDI QIDQ820149

N. E. Zubov

Publication date: 6 April 2006

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

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

zbMATH Keywords

graph theoryparameterized complexityinduced path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (14)

A general framework for path convexities ⋮ Graph editing to a fixed target ⋮ Algorithmic Aspects of Monophonic Convexity ⋮ The \(k\)-in-a-path problem for claw-free graphs ⋮ Strict betweennesses induced by posets as well as by graphs ⋮ The strength of Dantzig-Wolfe reformulations for the stable set and related problems ⋮ On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Complexity results related to monophonic convexity ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ Complexity aspects of \(\ell\)-chord convexities ⋮ Multiple hypernode hitting sets and smallest two-cores with targets ⋮ Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets ⋮ Few induced disjoint paths for \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The strong perfect graph theorem
• The directed subgraph homeomorphism problem
• On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Induced circuits in planar graphs
• The complexity of induced minors and related problems
• On the parameterized complexity of short computation and factorization
• Perfect Code is \(W[1\)-complete]
• The Turing way to parameterized complexity
• Graph minors. XIII: The disjoint paths problem
• Maximal Flow Through a Network
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On the Computational Complexity of Combinatorial Problems
• Algorithmic Aspects of Vertex Elimination on Graphs
• Non-interfering network flows

This page was built for publication: Chordless paths through three vertices