Jump number maximization for proper interval graphs and series-parallel graphs

DOI10.1016/S0020-0255(98)10081-6zbMath0960.05095OpenAlexW2069278216MaRDI QIDQ1818782

Ruay-Shiung Chang

Publication date: 10 May 2001

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0255(98)10081-6

zbMATH Keywords

jump numberseries-parallel graphsproper interval graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

The interval-merging problem ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ Minimal classes of graphs of unbounded clique-width

Cites Work

• Linear algorithm for optimal path cover problem on interval graphs
• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• Finding Hamiltonian circuits in interval graphs
• A combinatorial bijection between linear extensions of equivalent orders
• Computing the bump number is easy
• The edge Hamiltonian path problem is NP-complete
• Optimal covering of cacti by vertex-disjoint paths
• Some simplified NP-complete graph problems
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The NP-completeness column: an ongoing guide
• An Optimal Solution for the Channel-Assignment Problem
• The NP-Completeness of Edge-Coloring
• The Recognition of Series Parallel Digraphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Duality in Networks: Roses, Bouquets, and Cut‐Sets; Trees, Forests and Polygons
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Jump number maximization for proper interval graphs and series-parallel graphs