Chordless paths through three vertices

DOI10.1016/J.TCS.2005.10.021zbMATH Open1086.68102OpenAlexW2144784192MaRDI QIDQ820149FDOQ820149

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

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

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)

Cites Work

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

Cited In (17)

• 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
• A general framework for path convexities
• Graph editing to a fixed target
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Complexity aspects of \(\ell\)-chord convexities
• 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
• Induced Disjoint Paths in 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)