Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

From MaRDI portal
Publication:1242450

DOI10.1016/S0022-0000(76)80045-1zbMath0367.68034WikidataQ55952666 ScholiaQ55952666MaRDI QIDQ1242450

Kellogg S. Booth, George S. Lueker

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)



Mathematics Subject Classification ID

Trees (05C05) General topics in the theory of software (68N01) Algorithms in computer science (68W99)


Related Items

An optimal algorithm to recognize Robinsonian dissimilarities, CPG graphs: some structural and hardness results, Cyclability in graph classes, The recognition of geodetically connected graphs, Common intervals of trees, Consecutive retrieval property -- revisited, Edge intersection graphs of \(L\)-shaped paths in grids, Chronological rectangle digraphs, Largest chordal and interval subgraphs faster than \(2^n\), Optimal interval scheduling with a resource constraint, Max point-tolerance graphs, On recognition of threshold tolerance graphs and their complements, Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths, Recognizing and representing proper interval graphs in parallel using merging and sorting, Recognizing graphs without asteroidal triples, Reconstruction of interval graphs, An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem, Graph classes with structured neighborhoods and algorithmic applications, Recognition and characterization of chronological interval digraphs, An improved algorithm for the red-blue hitting set problem with the consecutive ones property, A characterization of the single-peaked domain, Tree-representation of set families and applications to combinatorial decompositions, A new perspective on clustered planarity as a combinatorial embedding problem, Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms, Edge search number of cographs, The firefighter problem on graph classes, The shield that never was: societies with single-peaked preferences are more open to manipulation and control, Linear-time recognition of Helly circular-arc models and graphs, Reasoning about visibility, Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances, Almost every graph is divergent under the biclique operator, Bandwidth of convex bipartite graphs and related graphs, Linear algorithm for optimal path cover problem on interval graphs, Backup 2-center on interval graphs, \(L(2,1)\)-labeling of perfect elimination bipartite graphs, An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals, Subgraphs of 4-regular planar graphs, A simpler linear-time recognition of circular-arc graphs, Domination in convex and chordal bipartite graphs, Bipartite graphs, upward drawings, and planarity, A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix, An optimal greedy heuristic to color interval graphs, New sequential and parallel algorithms for interval graph recognition, A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas-Eddy class, Certifying algorithms, 2-layer right angle crossing drawings, On the bend-number of planar and outerplanar graphs, Intersection representations of matrices by subtrees and unicycles on graphs, Packing of one-dimensional bins with contiguous selection of identical items: an exact method of optimal solution, Interval graph representation with given interval and intersection lengths, Minimal obstructions for partial representations of interval graphs, \texttt{PQser:} a Matlab package for spectral seriation, Finding outer-connected dominating sets in interval graphs, A linear-time algorithm for proper interval graph recognition, Simple linear time recognition of unit interval graphs, A linear-time algorithm for drawing a planar graph on a grid, The list distinguishing number equals the distinguishing number for interval graphs, Bipartite permutation graphs with application to the minimum buffer size problem, A branch-and-cut approach to the crossing number problem, Benders decomposition for set covering problems. Almost satisfying the consecutive ones property, Strict chordal and strict split digraphs, Circular-arc hypergraphs: rigidity via connectedness, Counting endpoint sequences for interval orders and interval graphs, Line-distortion, bandwidth and path-length of a graph, Fixed-parameter complexity of minimum profile problems, Interval competition graphs of symmetric digraphs, Strip planarity testing for embedded planar graphs, Extending partial representations of proper and unit interval graphs, Upward drawings of triconnected digraphs., Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, On counting interval lengths of interval graphs, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, Approximation algorithm for coloring of dotted interval graphs, A faster algorithm for finding minimum Tucker submatrices, Common intervals of multiple permutations, On probe permutation graphs, Branchwidth of chordal graphs, Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs, A new characterization of matrices with the consecutive ones property, Computing compatible tours for the symmetric traveling salesman problem, Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Consecutive block minimization is 1.5-approximable, Labelling algorithms for paired-domination problems in block and interval graphs, A simple algorithm to find Hamiltonian cycles in proper interval graphs, On the computational complexity of vertex integrity and component order connectivity, On compact and efficient routing in certain graph classes, Recognizing edge clique graphs among interval graphs and probe interval graphs, Preemptive scheduling and antichain polyhedra, The neighbour-scattering number can be computed in polynomial time for interval graphs, A linear time recognition algorithm for proper interval graphs, Algorithms for maximum independent set in convex bipartite graphs, Testing planarity of geometric automorphisms in linear time, Red-blue covering problems and the consecutive ones property, The simultaneous consecutive ones problem, The clique-separator graph for chordal graphs, Recognizing graphs with fixed interval number is NP-complete, A nonfactorial algorithm for testing isomorphism of two graphs, Circular representation problem on hypergraphs, On the isomorphism problem for Helly circular-arc graphs, On edge intersection graphs of paths with 2 bends, Optimal patchings for consecutive ones matrices, Optimal greedy algorithms for indifference graphs, A faster algorithm to recognize undirected path graphs, On the iterated edge-biclique operator, The haplotyping problem: an overview of computational models and solutions, Can transitive orientation make sandwich problems easier?, Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems, The complexity of planarity testing, Simple algorithms for partial and simultaneous rectangular duals with given contact orientations, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, Efficient algorithms for checking the atomicity of a run of read and write operations, On the \(k\)-coloring of intervals, The arborescence-realization problem, Hamiltonian problems in directed graphs with simple row patterns, Permuting matrices to avoid forbidden submatrices, Paired domination on interval and circular-arc graphs, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, Set covering with almost consecutive ones property, On the recognition of permuted bottleneck Monge matrices, Happy set problem on subclasses of co-comparability graphs, Finding geometric representations of apex graphs is NP-hard, Isomorphism testing for \(T\)-graphs in FPT, Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage, Upward planarity testing, Essential obstacles to Helly circular-arc graphs, Weighted independent perfect domination on cocomparability graphs, Robinsonian matrices: recognition challenges, Intersection graphs of Helly families of subtrees, Exact square coloring of certain classes of graphs: complexity and algorithms, Drawing planar graphs using the canonical ordering, Maximum planar subgraphs and nice embeddings: Practical layout tools, On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, Extending partial representations of interval graphs, Quasi-threshold graphs, On compiling structured CNFs to OBDDs, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Signed edge domination number of interval graphs, Chronological rectangle digraphs which are two-terminal series-parallel, Some families of trees arising in permutation analysis, Cleaning interval graphs, Treetopes and their graphs, The conditional covering problem on unweighted interval graphs with nonuniform coverage radius, Normal Helly circular-arc graphs and its subclasses, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs, Affine and projective tree metric theorems, A fully dynamic graph algorithm for recognizing interval graphs, A new planarity test, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Breakpoint distance and PQ-trees, Graph isomorphism and identification matrices: Sequential algorithms, Algorithmic aspects of clique-transversal and clique-independent sets, New results on induced matchings, Detecting fixed patterns in chordal graphs in polynomial time, Network construction with subgraph connectivity constraints, A conjunctive parallelogram model for Pick any/\(n\) data, Relaxing the constraints of clustered planarity, On coalescence analysis using genealogy rooted trees, On some tractable and hard instances for partial incentives and target set selection, Character-based phylogeny construction and its application to tumor evolution, Drawing borders efficiently, Convex \((0, 1)\)-matrices and their epitopes, A characterization of interval orders with semiorder dimension two, A Lex-BFS-based recognition algorithm for Robinsonian matrices, Beyond level planarity: cyclic, torus, and simultaneous level planarity, Recovering the structure of random linear graphs, Maximum rooted connected expansion, Simultaneous FPQ-ordering and hybrid planarity testing, A characterization of graphs with interval two-step graphs, Short encodings of planar graphs and maps, Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results, An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph, Fixed edge-length graph drawing is NP-hard, Stable matching with preferences derived from a psychological model, \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited, The co-secure domination in proper interval graphs, A good submatrix is hard to find, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, Lattice-based similarity measures between ordered trees, Planar drawings of fixed-mobile bigraphs, A type of algebraic structure related to sets of intervals, Scheduling preemptive jobs with precedence constraints on parallel machines, Precedence thinness in graphs, Advancements on SEFE and partitioned book embedding problems, Structured preferences: a literature survey, Clique partitioning with value-monotone submodular cost, Parameterized complexity of set-restricted disjoint paths on chordal graphs, A note on the consecutive ones submatrix problem., The weighted sitting closer to friends than enemies problem in the line, Obtaining matrices with the consecutive ones property by row deletions, A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs, Extending partial representations of subclasses of chordal graphs, Polynomial-time local-improvement algorithm for consecutive block minimization, Linear algorithms for red and blue domination in convex bipartite graphs, Minimising the number of gap-zeros in binary matrices, Towards a compact SAT-based encoding of itemset mining tasks, Cyclic arrangements with minimum modulo \(m\) winding numbers, Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs, Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid, On the Complexity of Finding a Potential Community, A Simple and Optimal Algorithm for Strict Circular Seriation, On Embeddability of Unit Disk Graphs onto Straight Lines, Unnamed Item, Testing superperfection of k-trees, Computing a dominating pair in an asteroidal triple-free graph in linear time, A linear algorithm for the maximal planar subgraph problem, Planarity Algorithms via PQ-Trees (Extended Abstract), Deferred-query—An efficient approach for problems on interval and circular-arc graphs, Edge Search Number of Cographs in Linear Time, A simulated annealing algorithm for the maximum planar subgraph problem, Reconstruction of Interval Graphs, On the Generalised Character Compatibility Problem for Non-branching Character Trees, Bijective comparison of optimal planarity algorithms, The round-up property of the fractional chromatic number for proper circular arc graphs, Branch-and-bound techniques for the maximum planar subgraph problem∗, On embeddability of unit disk graphs onto straight lines, \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs, Temporal interval cliques and independent sets, Extending partial representations of circular-arc graphs, Embedding graphs in the torus in linear time, Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs, Fair allocation algorithms for indivisible items under structured conflict constraints, Independent set under a change constraint from an initial solution, Maintaining triconnected components under node expansion, Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, The firebreak problem, Synchronized Planarity with Applications to Constrained Planarity Problems, Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition, Recognizing interval bigraphs by forbidden patterns, On the edge‐biclique graph and the iterated edge‐biclique operator, Algorithmic aspects of paired disjunctive domination in graphs, Sometimes travelling is easy: The master tour problem, Interval graphs with side (and size) constraints, Planarity for clustered graphs, \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs, On computing optimal linear diagrams, Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs, Morphing rectangular duals, On semi-transitive orientability of split graphs, Partial and simultaneous transitive orientations via modular decompositions, Achieving feasibility for clustered traveling salesman problems using PQ‐trees, An annotated review on graph drawing and its applications, Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang, Finding geometric representations of apex graphs is \textsf{NP}-hard, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Min-Orderable Digraphs, Unnamed Item, Recognizing Stick Graphs with and without Length Constraints, Reconfiguration of Spanning Trees with Many or Few Leaves, Exploring the complexity boundary between coloring and list-coloring, A 3-approximation for the pathwidth of Halin graphs, Efficient algorithms for independent Roman domination on some classes of graphs, Total domination in interval graphs, Total domination in interval graphs, On the Iterated Biclique Operator, Unnamed Item, Happy set problem on subclasses of co-comparability graphs, The two basic linear time Planarity algorithms: Are they the same?, On the complexity of the maximum biplanar subgraph problem, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Efficient algorithms for inferring evolutionary trees, Biclique graphs and biclique matrices, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Unnamed Item, Unnamed Item, Temporal graph classes: a view through temporal separators, Triangulating planar graphs while minimizing the maximum degree, Recognition and drawing of stick graphs, Preemptive hybrid flowshop scheduling problem of interval orders, Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs, Characterizing star-PCGs, Parameterized complexity of graph planarity with restricted cyclic orders, On Physical Mapping and the consecutive ones property for sparse matrices, Treemaps for Directed Acyclic Graphs, On \(H\)-topological intersection graphs, Graph classes and the switch Markov chain for matchings, Two strikes against perfect phylogeny, Fast incremental planarity testing, Graph isomorphism restricted by lists, Complexity and algorithms for semipaired domination in graphs, Computing k-modal embeddings of planar digraphs, On the generation of bicliques of a graph, Maximizing dominance in the plane and its applications, Stackelberg packing games, Linear-Time Recognition of Probe Interval Graphs, Unnamed Item, Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs, Unnamed Item, A Pfaffian formula for matching polynomials of outerplanar graphs, Quantitative Restrictions on Crossing Patterns, Simultaneous Embedding, PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT, An Optimal Algorithm for Strict Circular Seriation, Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs, Periodic assignment and graph colouring, Recognition of \(d\)-dimensional Monge arrays, Algorithms for interval catch digraphs, Neighborhood perfect graphs, Arboricity and bipartite subgraph listing algorithms, A linear algorithm for embedding planar graphs using PQ-trees, Rectilinear planar layouts and bipolar orientations of planar graphs, Finding small simple cycle separators for 2-connected planar graphs, Characterizations of two classes of digraphs, Finding the minimum bandwidth of an interval graph, Safe sets in graphs: graph classes and structural parameters, Planarity testing in parallel, Bipartite permutation graphs, Finding minimum height elimination trees for interval graphs in polynomial time, Testing a mixture model of single-peaked preferences, Graph graphics: Theory and practice, On-line sorting of twisted sequences in linear time, Testing for class membership in multi-parent hierarchies, The maximum k-colorable subgraph problem for chordal graphs, Proper interval graphs and the guard problem, Efficiently solvable special cases of hard combinatorial optimization problems, On the domatic number of interval graphs, A unified approach to domination problems on interval graphs, Total domination in interval graphs revisited, An efficient parallel algorithm for planarity, Restrictions of minimum spanner problems, Algorithmic aspects of intersection graphs and representation hypergraphs, On minimum intersection of two minimum dominating sets of interval graphs, Recognizing single-peaked preferences on a tree, Recognition of Robinsonian dissimilarities, Secure domination in proper interval graphs, Unit disk graph recognition is NP-hard, New results on drawing angle graphs, Satisfiability problems on intervals and unit intervals, On complexity of multidistance graph recognition in \(\mathbb{R}^1\), An efficient PQ-graph algorithm for solving the graph-realization problem, A monadic second-order definition of the structure of convex hypergraphs., Sublinear approximation algorithms for boxicity and related problems, PC trees and circular-ones arrangements., A simple algorithm for finding a cycle of length greater than three and without diagonals, On linear and circular structure of (claw, net)-free graphs, A large set of torus obstructions and how they were discovered, On minimal augmentation of a graph to obtain an interval graph, Optimal packing and covering in the plane are NP-complete, Local and union boxicity, Fully dynamic representations of interval graphs, On the thickness of graphs of given degree, Representations of graphs and networks (coding, layouts and embeddings), Algorithmic aspects of semitotal domination in graphs, Optimal canonization of all substrings of a string, On finding the minimum bandwidth of interval graphs, Tractabilities and intractabilities on geometric intersection graphs, Finding a potential community in networks, On the classes of interval graphs of limited nesting and count of lengths, The eternal dominating set problem for interval graphs, List matrix partitions of graphs representing geometric configurations, Dynamic monopolies for interval graphs with bounded thresholds, A simple algorithm for secure domination in proper interval graphs, Simultaneous embedding: edge orderings, relative positions, cutvertices, A new characterization of proper interval graphs, Processor optimization for flow graphs, Finding maximum edge bicliques in convex bipartite graphs, Hardness results on the gapped consecutive-ones property problem, Optimal linear arrangements using betweenness variables, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Efficient parallel recognition of some circular arc graphs. I, Paths in interval graphs and circular arc graphs, Computing the branchwidth of interval graphs, Polynomial and APX-hard cases of the individual haplotyping problem, Parameterized algorithms for conflict-free colorings of graphs, One more polynomial complete consecutive retrieval problem, A recognition algorithm for the intersection graphs of paths in trees, Representing triangulated graphs in stars, A note on the Hamiltonian circuit problem on directed path graphs, A fast bipartite network flow algorithm for selective assembly, Phylogenetic graph models beyond trees, On the complexity of the k-chain subgraph cover problem, A polynomially solvable class of quadratic semi-assignment problems, On testing consecutive-ones property in parallel, On probe interval graphs, On the consecutive ones property, Distance paired-domination problems on subclasses of chordal graphs, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, A selected tour of the theory of identification matrices, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Computational implementation of Fujishige's graph realizability algorithm, Finding Hamiltonian circuits in proper interval graphs, Modular decomposition and transitive orientation, Matrix sandwich problems, On counting planar embeddings, A fast algorithm for maximum integral two-commodity flow in planar graphs, Finding Hamiltonian circuits in interval graphs, A genetic algorithm for determining the thickness of a graph, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, Interval graphs and maps of DNA, Reconstruction graphs and testing their properties in a relational spatial database, Finding the closed partition of a planar graph, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs, Modules in Robinson Spaces, O(n2) algorithms for graph planarization, Minimax problems with bitonic matrices, The frame dimension and the complete overlap dimension of a graph, AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS, Unnamed Item, Computing the clique-separator graph for an interval graph in linear time, Efficient algorithms for centers and medians in interval and circular-arc graphs, Identifying Codes in Hereditary Classes of Graphs and VC-Dimension, Induced disjoint paths in circular-arc graphs in linear time, AN APPLICATION OF ST-NUMBERING TO SECRET KEY AGREEMENT, Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT, On Edge Intersection Graphs of Paths with 2 Bends, Interval bigraphs and circular arc graphs, Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs, Approximation Algorithms for Not Necessarily Disjoint Clustered TSP, An efficient graph planarization two‐phase heuristic, On Compiling Structured CNFs to OBDDs, A simple linear-time algorithm for computing the center of an interval graph, Polynomial-time self-reducibility: theoretical motivations and practical results∗, Injective coloring of some subclasses of bipartite graphs and chordal graphs, Succinct encodings for families of interval graphs, Vertices removal for feasibility of clustered spanning trees, Efficient algorithms for computing the reliability of permutation and interval graphs, Minimal Obstructions for Partial Representations of Interval Graphs, Iterated local search for consecutive block minimization, Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time, Clustered planarity with pipes, Characterizing interval graphs which are probe unit interval graphs, A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS, Defragmentation of permutation tables with four columns, The seriation problem in the presence of a double Fiedler value, A polynomial algorithm for weighted scattering number in interval graphs, A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs, Group control for consent rules with consecutive qualifications, Safe Sets in Graphs: Graph Classes and Structural Parameters, Mixed Search Number of Permutation Graphs, Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs, Hanani-Tutte for radial planarity. II, Mixed Search Number and Linear-Width of Interval and Split Graphs, A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs, Hanani-Tutte for Radial Planarity II, Beyond Level Planarity, A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs, Extending partial representations of rectangular duals with given contact orientations, On the complexity of recognizing Stick, BipHook and max point-tolerance graphs, Classes of perfect graphs, Parameterized complexity of graph planarity with restricted cyclic orders, An algorithm for reliability analysis of planar graphs, Edge-intersection graphs of grid paths: the bend-number, Recognition of probe proper interval graphs, Unnamed Item, On Robinsonian dissimilarities, the consecutive ones property and latent variable models, Computing a minimum outer-connected dominating set for the class of chordal graphs, A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph, Threshold tolerance graphs, An analysis of heuristics for graph planarization, A characterization of the single-crossing domain, Burning Two Worlds, An optimal algorithm to find minimum k-hop dominating set of interval graphs, Crossing-constrained hierarchical drawings, Blocks of Hypergraphs, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row, How to Cut a Graph into Many Pieces, Tractability Results for the Consecutive-Ones Property with Multiplicity, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, The travelling salesman and the PQ-tree, The complete optimal stars-clustering-tree problem, A REVIEW OF TREE CONVEX SETS TEST, Dynamic programming and lower-bound approaches to the minimum binding problem, A metric for evaluating software architecture and communication models consistency, On the interval completion of chordal graphs, Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results, NP-completeness results for edge modification problems, New tractable classes for default reasoning from conditional knowledge bases, Mixed search number and linear-width of interval and split graphs, A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs, ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES, Graph Simultaneous Embedding Tool, GraphSET, Optimal parallel algorithm for shortest-paths problem on interval graphs, Filters for Efficient Composition of Weighted Finite-State Transducers, Algorithmic approaches for the single individual haplotyping problem, Deferred-query: An efficient approach for some problems on interval graphs, The Monotone Circuit Value Problem with Bounded Genus Is in NC, Bounded Embeddings of Graphs in the Plane, Consecutive Ones Property Testing: Cut or Swap, Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, Characterizing path graphs by forbidden induced subgraphs, Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage, The Interval Count of a Graph, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, A simulated annealing algorithm for determining the thickness of a graph, Decomposition of integer matrices and multileaf collimator sequencing, Uniquely Restricted Matchings in Interval Graphs, A heuristic and an exact method for the gate matrix connection cost minimization problem, Weighted irredundance of interval graphs., Efficient algorithms for interval graphs and circular-arc graphs, An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs



Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1242450&oldid=13326707"
Powered by MediaWiki