Linearizing partial search orders

DOI10.1007/978-3-031-15914-5_31MaRDI QIDQ6039439zbMATH OpenOpenAlexFDO

Authors Robert Scheffler

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

end-vertex problemgraph searchLBFSMCSpartial ordersearch tree recognition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: In recent years, questions about the construction of special orderings of a given graph search were studied by several authors. On the one hand, the so called end-vertex problem introduced by Corneil et al. in 2010 asks for search orderings ending in a special vertex. On the other hand, the problem of finding orderings that induce a given search tree was introduced already in the 1980s by Hagerup and received new attention most recently by Beisegel et al. Here, we introduce a generalization of some of these problems by studying the question whether there is a search ordering that is a linear extension of a given partial order on a graph's vertex set. We show that this problem can be solved in polynomial time on chordal bipartite graphs for LBFS, which also implies the first polynomial-time algorithms for the end-vertex problem and two search tree problems for this combination of graph class and search. Furthermore, we present polynomial-time algorithms for LBFS and MCS on split graphs which generalize known results for the end-vertex and search tree problems.

Recommendations

• Partial order multiway search
• scientific article; zbMATH DE number 1962001
• Searching in 2-dimensional partial orders
• scientific article; zbMATH DE number 2101003
• The linear ordering problem: instances, search space analysis and algorithms
• Searching in dynamic tree-like partial orders
• Efficient searching with linear constraints
• An ordering linear unification algorithm
• scientific article; zbMATH DE number 3882490
• The linear ordering problem revisited

Cites work

• A general label search to investigate classical graph search algorithms
• A new LBFS-based algorithm for cocomparability graph recognition
• A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A tie-break model for graph search
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Efficient Planarity Testing
• End-vertices of LBFS of (AT-free) bigraphs
• Graph searches and their end vertices
• Influence of the tie-break rule on the end-vertex problem
• Maximum cardinality search for computing minimal triangulations of graphs
• Minimal vertex separators of chordal graphs
• On end-vertices of lexicographic breadth first searches
• On the end-vertex problem of graph searches
• Recognizing graph search trees
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The LBFS structure and recognition of interval graphs
• The recognition problem of graph search trees

Cited in

(8)

• scientific article; zbMATH DE number 2101003 (Why is no real title available?)
• Graph Search Trees and Their Leaves
• Recognizing LBFS trees of bipartite graphs
• On the leaves of graph search trees
• The partial search order problem
• Computing Hamiltonian paths with partial order restrictions
• Graph search trees and the Intermezzo problem
• Partial search orderings for MCS on chordal graphs via clique graph decomposition

This page was built for publication: Linearizing partial search orders

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