Extending partial representations of interval graphs (Q2408095): Difference between revisions

Latest revision as of 12:10, 14 July 2024

scientific article; zbMATH DE number 5916968

Extending Partial Representations of Interval Graphs

Language	Label	Description	Also known as
English	Extending partial representations of interval graphs	scientific article; zbMATH DE number 5916968	Extending Partial Representations of Interval Graphs

Statements

instance of

scholarly article

0 references

title

Extending partial representations of interval graphs (English)

0 references

Extending Partial Representations of Interval Graphs (English)

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Lecture Notes in Computer Science

0 references

publication date

9 October 2017

0 references

1 July 2011

0 references

full work available at URL

https://arxiv.org/abs/1306.2182

0 references

zbMATH Keywords

interval graphs

0 references

partial representation extension

0 references

PQ-trees

0 references

linear-time algorithm

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Maintaining knowledge about temporal intervals

0 references

Q5417619

0 references

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

0 references

Graph Classes: A Survey

0 references

A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs

0 references

The LBFS Structure and Recognition of Interval Graphs

0 references

NP completeness of the edge precoloring extension problem on bipartite graphs

0 references

Incidence matrices and interval graphs

0 references

Algorithmic graph theory and perfect graphs

0 references

Complexity and algorithms for reasoning about time

0 references

Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs

0 references

Simultaneous Interval Graphs

0 references

Reasoning about temporal relations

0 references

Optimal greedy algorithms for indifference graphs

0 references

NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

0 references

Topics in Intersection Graph Theory

0 references

Graph Drawing

0 references

Q5588432

0 references

Algorithmic Aspects of Vertex Elimination on Graphs

0 references

Bounded Representations of Interval and Proper Interval Graphs

0 references

Completing orientations of partially oriented graphs

0 references

Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems

0 references

Contact Representations of Planar Graphs: Extending a Partial Representation is Hard

0 references

Extending Partial Representations of Circle Graphs

0 references

The partial visibility representation extension problem

0 references

Q3344239

0 references

Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing

0 references

$O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs

0 references

The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs

0 references

Extending Partial Representations of Function Graphs and Permutation Graphs

0 references

Extending partial representations of proper and unit interval graphs

0 references

Extending partial representations of subclasses of chordal graphs

0 references

Extending partial representations of interval graphs

0 references

On the Classes of Interval Graphs of Limited Nesting and Count of Lengths

0 references

Minimal Obstructions for Partial Representations of Interval Graphs

0 references

Interval Graph Representation with Given Interval and Intersection Lengths

0 references

An Incremental Linear-Time Algorithm for Recognizing Interval Graphs

0 references

Representation of a finite graph by a set of intervals on the real line

0 references

On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs

0 references

Sur deux propriétés des classes d'ensembles

0 references

Linear-time recognition of circular-arc graphs

0 references

Realizing Interval Graphs with Size and Distance Constraints

0 references

Q4138414

0 references

Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory

0 references

Q4352951

0 references

Testing Planarity of Partially Embedded Graphs

0 references

Identifiers

zbMATH Open document ID

1371.05190

0 references

1331.68107

0 references

DOI

10.1007/s00453-016-0186-z

0 references

10.1007/978-3-642-20877-5_28

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2408095

@@ Property / cites work @@
+Maintaining knowledge about temporal intervals
@@ Property / cites work: Maintaining knowledge about temporal intervals / rank @@
+Normal rank
@@ Property / cites work @@
+Q5417619
@@ Property / cites work: Q5417619 / rank @@
+Normal rank
@@ Property / cites work @@
+Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
+Normal rank
@@ Property / cites work @@
+Graph Classes: A Survey
@@ Property / cites work: Graph Classes: A Survey / rank @@
+Normal rank
@@ Property / cites work @@
+A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
+Normal rank
@@ Property / cites work @@
+The LBFS Structure and Recognition of Interval Graphs
+Normal rank
@@ Property / cites work @@
+NP completeness of the edge precoloring extension problem on bipartite graphs
+Normal rank
@@ Property / cites work @@
+Incidence matrices and interval graphs
@@ Property / cites work: Incidence matrices and interval graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic graph theory and perfect graphs
@@ Property / cites work: Algorithmic graph theory and perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity and algorithms for reasoning about time
+Normal rank
@@ Property / cites work @@
+Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
+Normal rank
@@ Property / cites work @@
+Simultaneous Interval Graphs
@@ Property / cites work: Simultaneous Interval Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Reasoning about temporal relations
@@ Property / cites work: Reasoning about temporal relations / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal greedy algorithms for indifference graphs
@@ Property / cites work: Optimal greedy algorithms for indifference graphs / rank @@
+Normal rank
@@ Property / cites work @@
+NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
+Normal rank
@@ Property / cites work @@
+Topics in Intersection Graph Theory
@@ Property / cites work: Topics in Intersection Graph Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Drawing
@@ Property / cites work: Graph Drawing / rank @@
+Normal rank
@@ Property / cites work @@
+Q5588432
@@ Property / cites work: Q5588432 / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic Aspects of Vertex Elimination on Graphs
+Normal rank
@@ Property / cites work @@
+Bounded Representations of Interval and Proper Interval Graphs
+Normal rank
@@ Property / cites work @@
+Completing orientations of partially oriented graphs
+Normal rank
@@ Property / cites work @@
+Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
+Normal rank
@@ Property / cites work @@
+Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
+Normal rank
@@ Property / cites work @@
+Extending Partial Representations of Circle Graphs
+Normal rank
@@ Property / cites work @@
+The partial visibility representation extension problem
+Normal rank
@@ Property / cites work @@
+Q3344239
@@ Property / cites work: Q3344239 / rank @@
+Normal rank
@@ Property / cites work @@
+Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
+Normal rank
@@ Property / cites work @@
+$O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
+Normal rank
@@ Property / cites work @@
+The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
+Normal rank
@@ Property / cites work @@
+Extending Partial Representations of Function Graphs and Permutation Graphs
+Normal rank
@@ Property / cites work @@
+Extending partial representations of proper and unit interval graphs
+Normal rank
@@ Property / cites work @@
+Extending partial representations of subclasses of chordal graphs
+Normal rank
@@ Property / cites work @@
+Extending partial representations of interval graphs
+Normal rank
@@ Property / cites work @@
+On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
+Normal rank
@@ Property / cites work @@
+Minimal Obstructions for Partial Representations of Interval Graphs
+Normal rank
@@ Property / cites work @@
+Interval Graph Representation with Given Interval and Intersection Lengths
+Normal rank
@@ Property / cites work @@
+An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
+Normal rank
@@ Property / cites work @@
+Representation of a finite graph by a set of intervals on the real line
+Normal rank
@@ Property / cites work @@
+On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
+Normal rank
@@ Property / cites work @@
+Sur deux propriétés des classes d'ensembles
@@ Property / cites work: Sur deux propriétés des classes d'ensembles / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-time recognition of circular-arc graphs
@@ Property / cites work: Linear-time recognition of circular-arc graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Realizing Interval Graphs with Size and Distance Constraints
+Normal rank
@@ Property / cites work @@
+Q4138414
@@ Property / cites work: Q4138414 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded, minimal, and short representations of unit interval and unit circular-arc graphs.  Chapter I: theory
+Normal rank
@@ Property / cites work @@
+Q4352951
@@ Property / cites work: Q4352951 / rank @@
+Normal rank
@@ Property / cites work @@
+Testing Planarity of Partially Embedded Graphs
@@ Property / cites work: Testing Planarity of Partially Embedded Graphs / rank @@
+Normal rank