Computing paths of large rank in planar frameworks deterministically

DOI10.4230/LIPICS.ISAAC.2023.32MaRDI QIDQ6953187zbMATH OpenFDO

Authors Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Giannos Stamoulis

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.32

zbMATH Keywords

irrelevant vertexlinear matroidlongest pathplanar graph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• A single-exponential time 2-approximation algorithm for treewidth
• Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• An analysis of approximations for maximizing submodular set functions—I
• An Improved Algorithm for Finding Cycles Through Elements
• Color-coding
• Determinant sums for undirected Hamiltonicity
• Deterministic truncation of linear matroids
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding topological subgraphs is fixed-parameter tractable
• Fixed-parameter tractability of maximum colored path and beyond
• Graph minors. XIII: The disjoint paths problem
• Graphs and geometry
• Hadwiger's conjecture is decidable
• Hitting topological minors is FPT
• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 1775441 (Why is no real title available?)
• scientific article; zbMATH DE number 2147947 (Why is no real title available?)
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Linkless and flat embeddings in 3-space and the unknot problem
• Matching theory
• Maximizing a monotone submodular function subject to a matroid constraint
• Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes
• Modification to Planarity is Fixed Parameter Tractable
• Narrow sieves for parameterized paths and packings
• Obtaining a planar graph by vertex deletion
• Odd cycle packing
• Parameterized algorithms
• Planarity Allowing Few Error Vertices in Linear Time
• Quickly excluding a planar graph
• Shortest cycles with monotone submodular costs
• The maximum labeled path problem
• The parameterized complexity of graph cyclability
• Tropical paths in vertex-colored graphs
• Vertex deletion parameterized by elimination distance and even less

This page was built for publication: Computing paths of large rank in planar frameworks deterministically

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