Dynamic representation of consecutive-ones matrices and interval graphs
| dc.contributor.author | Springer, William M., II, author | |
| dc.contributor.author | McConnell, Ross M., advisor | |
| dc.contributor.author | Ray, Indrajit, committee member | |
| dc.contributor.author | Bohm, Wim, committee member | |
| dc.contributor.author | Hulpke, Alexander, committee member | |
| dc.date.accessioned | 2015-08-27T03:57:03Z | |
| dc.date.available | 2015-08-27T03:57:03Z | |
| dc.date.issued | 2015 | |
| dc.description.abstract | We give an algorithm for updating a consecutive-ones ordering of a consecutive-ones matrix when a row or column is added or deleted. When the addition of the row or column would result in a matrix that does not have the consecutive-ones property, we return a well-known minimal forbidden submatrix for the consecutive-ones property, known as a Tucker submatrix, which serves as a certificate of correctness of the output in this case, in O(n log n) time. The ability to return such a certificate within this time bound is one of the new contributions of this work. Using this result, we obtain an O(n) algorithm for updating an interval model of an interval graph when an edge or vertex is added or deleted. This matches the bounds obtained by a previous dynamic interval-graph recognition algorithm due to Crespelle. We improve on Crespelle's result by producing an easy-to-check certificate, known as a Lekkerkerker-Boland subgraph, when a proposed change to the graph results in a graph that is not an interval graph. Our algorithm takes O(n log n) time to produce this certificate. The ability to return such a certificate within this time bound is the second main contribution of this work. | |
| dc.format.medium | born digital | |
| dc.format.medium | doctoral dissertations | |
| dc.identifier | Springer_colostate_0053A_12879.pdf | |
| dc.identifier.uri | http://hdl.handle.net/10217/166918 | |
| dc.language | English | |
| dc.language.iso | eng | |
| dc.publisher | Colorado State University. Libraries | |
| dc.relation.ispartof | 2000-2019 | |
| dc.rights | Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright. | |
| dc.subject | certifying algorithm | |
| dc.subject | interval graph | |
| dc.subject | Tucker matrix | |
| dc.subject | consecutive-ones matrix | |
| dc.subject | asteroidal triple | |
| dc.subject | Lekkerkerker-Boland | |
| dc.title | Dynamic representation of consecutive-ones matrices and interval graphs | |
| dc.type | Text | |
| dcterms.rights.dpla | This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Colorado State University | |
| thesis.degree.level | Doctoral | |
| thesis.degree.name | Doctor of Philosophy (Ph.D.) |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Springer_colostate_0053A_12879.pdf
- Size:
- 829.14 KB
- Format:
- Adobe Portable Document Format