Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths

DOI10.1007/978-3-642-31155-0_13zbMath1357.68077arXiv1410.3260OpenAlexW1492318137MaRDI QIDQ2904550

Aistis Atminas, Igor Razgon, Vadim V. Lozin

Publication date: 14 August 2012

Published in: Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.3260

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

The Micro-world of Cographs ⋮ The micro-world of cographs ⋮ Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ Vertex coloring of graphs with few obstructions ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Labelled induced subgraphs and well-quasi-ordering ⋮ Critical properties of bipartite permutation graphs ⋮ Unnamed Item ⋮ Coloring graphs without short cycles and long induced paths ⋮ Long induced paths in graphs ⋮ A Ramsey-type theorem for the matching number regarding connected graphs ⋮ Finding cactus roots in polynomial time ⋮ Colouring square-free graphs without long induced paths ⋮ Hereditary classes of graphs: a parametric approach ⋮ Fine-grained parameterized complexity analysis of graph coloring problems

This page was built for publication: Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths