Linear structure of bipartite permutation graphs and the longest path problem

DOI10.1016/j.ipl.2007.02.010zbMath1183.05071WikidataQ56639271 ScholiaQ56639271MaRDI QIDQ2379947

Ryuhei Uehara, Gabriel Valiente

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.02.010

zbMATH Keywords

graph algorithms; graph decomposition; linear time algorithms; bipartite permutation graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C38: Paths and cycles

05C75: Structural characterization of families of graphs

Related Items

The longest path problem has a polynomial solution on interval graphs, Labeling bipartite permutation graphs with a condition at distance two, The longest path problem is polynomial on cocomparability graphs, The Longest Path Problem is Polynomial on Cocomparability Graphs, A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs, The Longest Path Problem Is Polynomial on Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Bandwidth of chain graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• On approximating the longest path in a graph
• Bipartite permutation graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• Node-Deletion Problems on Bipartite Graphs
• Graph Classes: A Survey
• Algorithms and Computation