Linear structure of bipartite permutation graphs and the longest path problem

DOI10.1016/J.IPL.2007.02.010zbMATH Open1183.05071OpenAlexW2057303484WikidataQ56639271 ScholiaQ56639271MaRDI QIDQ2379947FDOQ2379947

Authors: 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

Recommendations

• scientific article; zbMATH DE number 2191997
• Bipartite permutation graphs
• scientific article; zbMATH DE number 1156661
• A linear algorithms for the two paths problem on permutation graphs
• A polynomial time algorithm for longest paths in biconvex graphs

zbMATH Keywords

graph algorithmsgraph decompositionlinear time algorithmsbipartite permutation graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Cites Work

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

Cited In (18)

• Tropical paths in vertex-colored graphs
• The longest path problem is polynomial on cocomparability graphs
• \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
• Labeling bipartite permutation graphs with a condition at distance two
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Path eccentricity of graphs
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Tractabilities and intractabilities on geometric intersection graphs
• Labelled well-quasi-order for permutation classes
• The longest path problem is polynomial on cocomparability graphs
• Linear-time algorithms for counting independent sets in bipartite permutation graphs
• The longest path problem has a polynomial solution on interval graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The Longest Path Problem Is Polynomial on Interval Graphs
• A polynomial time algorithm for longest paths in biconvex graphs
• A linear algorithms for the two paths problem on permutation graphs
• A polynomial kernel for bipartite permutation vertex deletion

This page was built for publication: Linear structure of bipartite permutation graphs and the longest path problem

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