scientific article

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

jump number interval graphs order dimension interval orders combinatorial optimization problems partial orders incomparability graphs Comparability graphs coefficient algorithms comparability graph recognition decomposing comparability graphs interval graph recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items

Schedule-induced posets, A \(k\)-structure generalization of the theory of 2-structures, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Finding the minimum bandwidth of an interval graph, On finding the jump number of a partial order by substitution decomposition, On transitive orientations with restricted covering graphs, Greedy posets for the bump-minimizing problem, On semi-\(P_ 4\)-sparse graphs, Scattering number and modular decomposition, The order-interval hypergraph of a finite poset and the König property, A new LBFS-based algorithm for cocomparability graph recognition, An algorithm for solving the jump number problem, A simple linear time algorithm to solve the MIST problem on interval graphs, On the closure of graphs under substitution, Satisfiability problems on intervals and unit intervals, Modular decomposition of hypergraphs, The mutual exclusion scheduling problem for permutation and comparability graphs., Succinct permutation graphs, Aggregation of monotone reciprocal relations with application to group decision making, Scheduling of project networks, Fully dynamic representations of interval graphs, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, Weak order polytopes., On the complexity of dynamic programming for sequencing problems with precedence constraints, Introduction à l'algorithmique des objets partagés, Unit disk graphs, The longest cycle problem is polynomial on interval graphs, A tight lower bound for primitivity in k-structures, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes, How to use the minimal separators of a graph for its chordal triangulation, Peakless functions on graphs, Graphs and topologies on discrete sets, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Another note on Dilworth's decomposition theorem., Bipartite bithreshold graphs, \(P_ 4\)-trees and substitution decomposition, Independent domination in finitely defined classes of graphs: polynomial algorithms, On probe permutation graphs, On the generation of circuits and minimal forbidden sets, Nesting of prime substructures in \(k-\)ary relations, Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs, Optimal pricing of capacitated networks, Preemptive hybrid flowshop scheduling problem of interval orders, Recognizing \(k\)-clique extendible orderings, Triangulating graphs with few \(P_4\)'s, Achromatic number is NP-complete for cographs and interval graphs, A polynomial algorithm for recognizing the \(\mathcal A\)-order class, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Modular decomposition and transitive orientation, On the pathwidth of chordal graphs, A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs, The number of nonisomorphic posets having 12 elements, Topological adjacency relations on \(Z^{n}\), Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs, The smallest graphs with niche number three