End-vertices of graph search algorithms

DOI10.1007/978-3-319-18173-8_22MaRDI QIDQ2947028zbMATH OpenOpenAlexFDO

Authors Dieter Kratsch, Mathieu Liedloff, Daniel Meister

Publication date 21 September 2015

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

Full work available at URL https://doi.org/10.1007/978-3-319-18173-8_22

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• On the end-vertex problem of graph searches
• End vertices of graph searches on bipartite graphs
• Influence of the tie-break rule on the end-vertex problem
• On end-vertices of lexicographic breadth first searches
• End-vertices of LBFS of (AT-free) bigraphs

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A Unified View of Graph Searching
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Determinant sums for undirected Hamiltonicity
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Exact exponential algorithms.
• Influence of the tie-break rule on the end-vertex problem
• Introduction to algorithms.
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• LexBFS-orderings and powers of chordal graphs
• On end-vertices of lexicographic breadth first searches

Cited in

(12)

• On end-vertices of lexicographic breadth first searches
• End simplicial vertices in path graphs
• Graph extremities defined by search algorithms
• A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph
• Influence of the tie-break rule on the end-vertex problem
• Graph searches and their end vertices
• On the end-vertex problem of graph searches
• End vertices of graph searches on bipartite graphs
• On the leaves of graph search trees
• Graph Search Trees and Their Leaves
• The partial search order problem
• End-vertices of LBFS of (AT-free) bigraphs

This page was built for publication: End-vertices of graph search algorithms

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