Graph searches and their end vertices

DOI10.1007/S00453-022-00981-5MaRDI QIDQ2165035zbMATH OpenOpenAlexFDO

Authors Guozhen Rong, Yixin Cao, Jianxin Wang, Zhifeng Wang

Publication date 18 August 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.09505

zbMATH Keywords

chordal graphweakly chordal graphmaximum cardinality searchend vertex of a graph search

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• Graph Searches and Their End Vertices.
• On the end-vertex problem of graph searches
• End vertices of graph searches on bipartite graphs
• End-vertices of graph search algorithms
• Influence of the tie-break rule on the end-vertex problem

Cites work

• scientific article; zbMATH DE number 176590 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• A Unified View of Graph Searching
• A four-sweep LBFS recognition algorithm for interval graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Graph Connectivity
• Algorithmic Aspects of Vertex Elimination on Graphs
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Depth-First Search and Linear Graph Algorithms
• Efficient Planarity Testing
• End vertices of graph searches on bipartite graphs
• End-vertices of graph search algorithms
• Graph extremities defined by search algorithms
• Graph-Theoretic Concepts in Computer Science
• Incidence matrices and interval graphs
• Influence of the tie-break rule on the end-vertex problem
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• On end-vertices of lexicographic breadth first searches
• On rigid circuit graphs
• On the complexity of \(k\)-SAT
• On the end-vertex problem of graph searches
• Power of Natural Semijoins
• Scheduling Graphs on Two Processors
• Separability generalizes Dirac's theorem
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Some aspects of perfect elimination orderings in chordal graphs
• The LBFS structure and recognition of interval graphs

Cited in

(5)

• 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
• Linearizing partial search orders
• Graph Search Trees and Their Leaves

This page was built for publication: Graph searches and their end vertices

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