On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs

DOI10.1016/j.tcs.2009.12.017zbMath1213.05250MaRDI QIDQ2268880

Mauro Mezzini

Publication date: 9 March 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.12.017

zbMATH Keywords

bipartite graphs; graph convexity; interval operators; simple paths; chordless paths; even-chorded paths

Mathematics Subject Classification ID

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Computing simple-path convex hulls in hypergraphs

Cites Work

• Unnamed Item
• Connections in acyclic hypergraphs
• Chordless paths through three vertices
• The strong perfect graph theorem
• Canonical and monophonic convexities in hypergraphs
• Characterizations of strongly chordal graphs
• On hypergraph acyclicity and graph chordality
• On the complexity of testing for odd holes and induced odd paths
• A fast algorithm for query optimization in universal-relation databases
• Convexities related to path properties on graphs
• Even-hole-free graphs part I: Decomposition theorem
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• Even-hole-free graphs part II: Recognition algorithm
• Algorithmic Aspects of Monophonic Convexity
• Convexity in Graphs and Hypergraphs
• Detecting even holes