Algorithms and Computation

DOI10.1007/b104582zbMath1116.05318MaRDI QIDQ5712173

Yushi Uno, Ryuhei Uehara

Publication date: 22 December 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b104582

zbMATH Keywords

graph classes; longest path problem; Efficient algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Secure total domination in chain graphs and cographs, Algorithmic aspects of total Roman {3}-domination in graphs, Total vertex-edge domination in graphs: Complexity and algorithms, Independent roman $\{3\}$-domination, Tropical paths in vertex-colored graphs, Transversals of longest paths, Guarantees for Existence of a Best Canonical Polyadic Approximation of a Noisy Low-Rank Tensor, Algorithmic complexity of weakly connected Roman domination in graphs, The Maximum Binary Tree Problem., Unnamed Item, Dendrograms, minimum spanning trees and feature selection, Algorithmic aspects of certified domination in graphs, Algorithmic aspects of total Roman ${2}$-domination in graphs, Algorithmic Aspects of Quasi-Total Roman Domination in Graphs, An approximation algorithm for the longest cycle problem in solid grid graphs, The longest path problem has a polynomial solution on interval graphs, \(L(2,1)\)-labeling of perfect elimination bipartite graphs, Algorithmic aspects of total Roman and total double Roman domination in graphs, The longest path problem is polynomial on cocomparability graphs, On partial Grundy coloring of bipartite graphs and chordal graphs, The maximum binary tree problem, Algorithmic aspects of secure connected domination in graphs, Algorithmic aspects of Roman domination in graphs, Hardness results of connected power domination for bipartite graphs and chordal graphs, Grundy coloring in some subclasses of bipartite graphs and their complements, Linear structure of bipartite permutation graphs and the longest path problem, Computing and counting longest paths on circular-arc graphs in polynomial time, QUBO formulations of the longest path problem, Complexity aspects of variants of independent Roman domination in graphs, Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time, The Longest Path Problem is Polynomial on Cocomparability Graphs, A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs, The Longest Path Problem Is Polynomial on Interval Graphs