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 simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A Unified View of Graph Searching
• 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

(14)

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

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)