Jump number maximization for proper interval graphs and series-parallel graphs
From MaRDI portal
Publication:1818782
DOI10.1016/S0020-0255(98)10081-6zbMath0960.05095OpenAlexW2069278216MaRDI QIDQ1818782
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
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
