Finding monotone paths in edge-ordered graphs

DOI10.1016/j.dam.2010.05.018zbMath1208.05061OpenAlexW2003994307MaRDI QIDQ602679

Gabriel Semanisin, Ján Katrenič

Publication date: 5 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.05.018

zbMATH Keywords

complexityascent\(k\)-pathedge-orderingmonotone path\(NP\)-completeness

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items (4)

Increasing paths in edge-ordered graphs: the hypercube and random graph ⋮ A class of graphs with depression three ⋮ Most edge‐orderings of K_n have maximal altitude ⋮ The depression of a graph and \(k\)-kernels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Altitude of wheels and wheel-like graphs
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• The depression of a graph and the diameter of its line graph
• Altitude of regular graphs with girth at least five
• Monotone paths in edge-ordered sparse graphs
• Trees with depression three
• Increasing paths in edge ordered graphs
• Divide-and-Color
• On Linear Time Minor Tests with Depth-First Search
• Color-coding
• Some Combinatorial Theorems on Monotonicity
• Large monotone paths in graphs with bounded degree

This page was built for publication: Finding monotone paths in edge-ordered graphs