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.05250OpenAlexW2049124187MaRDI 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 graphsgraph convexityinterval operatorssimple pathschordless pathseven-chorded paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Computing simple-path convex hulls in hypergraphs ⋮ Simplified frequency response computation of fractional order systems with multiple linear uncertainty structures ⋮ Inapproximability results related to monophonic convexity ⋮ An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs

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

This page was built for publication: On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs