Graph searches and their end vertices

DOI10.1007/S00453-022-00981-5OpenAlexW2946173551MaRDI QIDQ2165035FDOQ2165035

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)

Cites Work

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

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)