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

DOI10.1016/J.TCS.2009.12.017MaRDI QIDQ2268880zbMATH OpenOpenAlexFDO

Authors 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 graphschordless pathseven-chorded pathsgraph convexityinterval operatorssimple paths

Mathematics Subject Classification ID

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

Recommendations

• Parameterized complexity of set-restricted disjoint paths on chordal graphs
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• On the pathwidth of chordal graphs
• The \(k\)-disjoint paths problem on chordal graphs
• Several results on chordal bipartite graphs
• Complexity of certain functional variants of total domination in chordal bipartite graphs
• The Complexity of Finding Paths in Graphs with Bounded Independence Number
• On the interval completion of chordal graphs
• scientific article; zbMATH DE number 2086689
• The path partition problem and related problems in bipartite graphs

Cites work

• A fast algorithm for query optimization in universal-relation databases
• Algorithmic Aspects of Monophonic Convexity
• Canonical and monophonic convexities in hypergraphs
• Characterizations of strongly chordal graphs
• Chordless paths through three vertices
• Connections in acyclic hypergraphs
• Convexities related to path properties on graphs
• Convexity in Graphs and Hypergraphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• Detecting even holes
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs. I: Decomposition theorem
• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• On hypergraph acyclicity and graph chordality
• On the complexity of testing for odd holes and induced odd paths
• On the Desirability of Acyclic Database Schemes
• The strong perfect graph theorem

Cited in

(7)

• Simplified frequency response computation of fractional order systems with multiple linear uncertainty structures
• Computing simple-path convex hulls in hypergraphs
• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
• Inapproximability results related to monophonic convexity
• Parameterized and Exact Computation
• Parameterizing path partitions
• Chordless paths through three vertices

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

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