Chordless paths through three vertices

DOI10.1016/J.TCS.2005.10.021MaRDI QIDQ820149zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Parameterized and Exact Computation
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• scientific article; zbMATH DE number 4117882
• Parameterized algorithm for 3-path vertex cover
• On efficient coloring of chordless graphs

Cites work

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

Cited in

(16)

• Few induced disjoint paths for \(H\)-free graphs
• Multiple hypernode hitting sets and smallest two-cores with targets
• Strict betweennesses induced by posets as well as by graphs
• Parameterized and Exact Computation
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• The strength of Dantzig-Wolfe reformulations for the stable set and related problems
• Complexity results related to monophonic convexity
• The parameterized complexity of k-edge induced subgraphs
• Induced disjoint paths in claw-free graphs
• Graph editing to a fixed target
• Complexity aspects of -chord convexities
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• Algorithmic Aspects of Monophonic Convexity
• The \(k\)-in-a-path problem for claw-free graphs

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

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