Finding monotone paths in edge-ordered graphs
type: Item
instance of: scholarly article
title: Finding monotone paths in edge-ordered graphs
zbMATH Open document ID: 1208.05061
author: Gabriel Semanišin
author: Ján Katrenič
published in: Discrete Applied Mathematics
publication date: 2010-11-05T00:00:00Z
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5810757
zbMATH Keywords: ascent
zbMATH Keywords: monotone path
zbMATH Keywords: \(NP\)-completeness
zbMATH Keywords: complexity
zbMATH Keywords: edge-ordering
zbMATH Keywords: \(k\)-path
MaRDI profile type: Publication
full work available at URL: j.dam.2010.05.018
OpenAlex ID: W2003994307
cites work: Color-coding
cites work: On Linear Time Minor Tests with Depth-First Search
cites work: Q4659594
cites work: Altitude of regular graphs with girth at least five
cites work: Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
cites work: Some Combinatorial Theorems on Monotonicity
cites work: Q5488340
cites work: Q4681992
cites work: Q3619797
cites work: Altitude of wheels and wheel-like graphs
cites work: The depression of a graph and the diameter of its line graph
cites work: Increasing paths in edge ordered graphs
cites work: Q2934608
cites work: On approximating the longest path in a graph
cites work: Divide-and-Color
cites work: Q3740256
cites work: Trees with depression three
cites work: Q4231923
cites work: Monotone paths in edge-ordered sparse graphs
cites work: Large monotone paths in graphs with bounded degree
DOI: 10.1016/J.DAM.2010.05.018
description: scientific article; zbMATH DE number 5810757